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