Hex Artifact Content
Not logged in

Artifact 12244591e3a7308ea9d73326e9cdd03aab9e1376:


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 73 69 7a  n nc; }..int siz
01a0: 65 28 69 6e 74 20 61 29 0a 09 09 7b 20 72 65 74  e(int a)...{ ret
01b0: 75 72 6e 20 73 7a 5b 46 69 6e 64 28 61 29 5d 3b  urn sz[Find(a)];
01c0: 20 7d 0a 09 69 6e 74 20 46 69 6e 64 28 69 6e 74   }..int Find(int
01d0: 20 61 29 0a 09 09 7b 20 72 65 74 75 72 6e 20 75   a)...{ return u
01e0: 66 5b 61 5d 3d 3d 61 20 3f 20 61 20 3a 20 75 66  f[a]==a ? a : uf
01f0: 5b 61 5d 3d 46 69 6e 64 28 75 66 5b 61 5d 29 3b  [a]=Find(uf[a]);
0200: 20 7d 0a 09 62 6f 6f 6c 20 55 6e 69 6f 6e 28 69   }..bool Union(i
0210: 6e 74 20 61 2c 20 69 6e 74 20 62 29 0a 09 09 7b  nt a, int b)...{
0220: 0a 09 09 09 61 20 3d 20 46 69 6e 64 28 61 29 3b  ....a = Find(a);
0230: 0a 09 09 09 62 20 3d 20 46 69 6e 64 28 62 29 3b  ....b = Find(b);
0240: 0a 09 09 09 69 66 28 20 61 20 21 3d 20 62 20 29  ....if( a != b )
0250: 0a 09 09 09 7b 0a 09 09 09 09 69 66 28 20 73 7a  ....{.....if( sz
0260: 5b 61 5d 20 3e 3d 20 73 7a 5b 62 5d 20 29 20 73  [a] >= sz[b] ) s
0270: 77 61 70 28 61 2c 20 62 29 3b 0a 09 09 09 09 75  wap(a, b);.....u
0280: 66 5b 61 5d 20 3d 20 62 3b 0a 09 09 09 09 73 7a  f[a] = b;.....sz
0290: 5b 62 5d 20 2b 3d 20 73 7a 5b 61 5d 3b 0a 09 09  [b] += sz[a];...
02a0: 09 09 2d 2d 6e 63 3b 0a 09 09 09 7d 0a 09 09 09  ..--nc;....}....
02b0: 72 65 74 75 72 6e 20 28 61 21 3d 62 29 3b 0a 09  return (a!=b);..
02c0: 09 7d 0a 7d 3b 0a                                .}.};.