Hex Artifact Content
Not logged in

Artifact 734bdff2cfc3cb9d3b6f9eedd05ff2fdfb0e7edf:


0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a  ---------------.
0040: 2f 2f 20 55 6e 69 6f 6e 2d 46 69 6e 64 0a 2f 2f  // Union-Find.//
0050: 20 20 20 42 61 6c 61 6e 63 69 6e 67 20 2b 20 50     Balancing + P
0060: 61 74 68 2d 43 6f 6d 70 72 65 73 73 69 6f 6e 20  ath-Compression 
0070: 3a 20 4f 28 69 6e 76 41 63 6b 65 72 6d 61 6e 6e  : O(invAckermann
0080: 29 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64  ).//.// Verified
0090: 20 62 79 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 4d   by.//   - SRM M
00a0: 65 6d 62 65 72 20 50 69 6c 6f 74 20 32 20 44 69  ember Pilot 2 Di
00b0: 76 31 20 4c 56 32 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d  v1 LV2.//-------
00c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
00d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
00e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d  ----------------
00f0: 2d 2d 2d 2d 2d 2d 0a 0a 73 74 72 75 63 74 20 55  ------..struct U
0100: 6e 69 6f 6e 46 69 6e 64 0a 7b 0a 09 76 65 63 74  nionFind.{..vect
0110: 6f 72 3c 69 6e 74 3e 20 75 66 2c 20 73 7a 3b 0a  or<int> uf, sz;.
0120: 09 69 6e 74 20 6e 63 3b 0a 0a 09 55 6e 69 6f 6e  .int nc;...Union
0130: 46 69 6e 64 28 69 6e 74 20 4e 29 3a 20 75 66 28  Find(int N): uf(
0140: 4e 29 2c 20 73 7a 28 4e 2c 31 29 2c 20 6e 63 28  N), sz(N,1), nc(
0150: 4e 29 0a 09 09 7b 20 66 6f 72 28 69 6e 74 20 69  N)...{ for(int i
0160: 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 20 75 66  =0; i<N; ++i) uf
0170: 5b 69 5d 20 3d 20 69 3b 20 7d 0a 09 69 6e 74 20  [i] = i; }..int 
0180: 73 69 7a 65 28 29 0a 09 09 7b 20 72 65 74 75 72  size()...{ retur
0190: 6e 20 6e 63 3b 20 7d 0a 09 69 6e 74 20 46 69 6e  n nc; }..int Fin
01a0: 64 28 69 6e 74 20 61 29 0a 09 09 7b 20 72 65 74  d(int a)...{ ret
01b0: 75 72 6e 20 75 66 5b 61 5d 3d 3d 61 20 3f 20 61  urn uf[a]==a ? a
01c0: 20 3a 20 75 66 5b 61 5d 3d 46 69 6e 64 28 75 66   : uf[a]=Find(uf
01d0: 5b 61 5d 29 3b 20 7d 0a 09 62 6f 6f 6c 20 55 6e  [a]); }..bool Un
01e0: 69 6f 6e 28 69 6e 74 20 61 2c 20 69 6e 74 20 62  ion(int a, int b
01f0: 29 0a 09 09 7b 0a 09 09 09 61 20 3d 20 46 69 6e  )...{....a = Fin
0200: 64 28 61 29 3b 0a 09 09 09 62 20 3d 20 46 69 6e  d(a);....b = Fin
0210: 64 28 62 29 3b 0a 09 09 09 69 66 28 20 61 20 21  d(b);....if( a !
0220: 3d 20 62 20 29 0a 09 09 09 7b 0a 09 09 09 09 69  = b )....{.....i
0230: 66 28 20 73 7a 5b 61 5d 20 3e 3d 20 73 7a 5b 62  f( sz[a] >= sz[b
0240: 5d 20 29 20 73 77 61 70 28 61 2c 20 62 29 3b 0a  ] ) swap(a, b);.
0250: 09 09 09 09 75 66 5b 61 5d 20 3d 20 62 3b 0a 09  ....uf[a] = b;..
0260: 09 09 09 73 7a 5b 62 5d 20 2b 3d 20 73 7a 5b 61  ...sz[b] += sz[a
0270: 5d 3b 0a 09 09 09 09 2d 2d 6e 63 3b 0a 09 09 09  ];.....--nc;....
0280: 7d 0a 09 09 09 72 65 74 75 72 6e 20 28 61 21 3d  }....return (a!=
0290: 62 29 3b 0a 09 09 7d 0a 7d 3b 0a                 b);...}.};.