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 .}.};.