Artifact c818f654949cbd86aa8bba644f5b4e0d60ff1996:
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 09 2f 2f 20 53 65 6d 69 2d 63 6f 6d }...// Semi-com
0210: 70 72 65 73 73 69 6f 6e 20 77 2e 6f 2e 20 72 65 pression w.o. re
0220: 63 75 72 73 69 6f 6e 2e 0a 09 09 2f 2f 7b 20 77 cursion....//{ w
0230: 68 69 6c 65 28 75 66 5b 61 5d 20 21 3d 20 61 29 hile(uf[a] != a)
0240: 20 61 3d 75 66 5b 61 5d 3d 75 66 5b 75 66 5b 61 a=uf[a]=uf[uf[a
0250: 5d 5d 3b 20 72 65 74 75 72 6e 20 61 3b 20 7d 0a ]]; return a; }.
0260: 09 62 6f 6f 6c 20 55 6e 69 6f 6e 28 69 6e 74 20 .bool Union(int
0270: 61 2c 20 69 6e 74 20 62 29 0a 09 09 7b 0a 09 09 a, int b)...{...
0280: 09 61 20 3d 20 46 69 6e 64 28 61 29 3b 0a 09 09 .a = Find(a);...
0290: 09 62 20 3d 20 46 69 6e 64 28 62 29 3b 0a 09 09 .b = Find(b);...
02a0: 09 69 66 28 20 61 20 21 3d 20 62 20 29 0a 09 09 .if( a != b )...
02b0: 09 7b 0a 09 09 09 09 69 66 28 20 73 7a 5b 61 5d .{.....if( sz[a]
02c0: 20 3e 3d 20 73 7a 5b 62 5d 20 29 20 73 77 61 70 >= sz[b] ) swap
02d0: 28 61 2c 20 62 29 3b 0a 09 09 09 09 75 66 5b 61 (a, b);.....uf[a
02e0: 5d 20 3d 20 62 3b 0a 09 09 09 09 73 7a 5b 62 5d ] = b;.....sz[b]
02f0: 20 2b 3d 20 73 7a 5b 61 5d 3b 0a 09 09 09 09 2d += sz[a];.....-
0300: 2d 6e 63 3b 0a 09 09 09 7d 0a 09 09 09 72 65 74 -nc;....}....ret
0310: 75 72 6e 20 28 61 21 3d 62 29 3b 0a 09 09 7d 0a urn (a!=b);...}.
0320: 7d 3b 0a };.