Differences From Artifact [12244591e3a7308e]:
- File
lib/typical/unionfind.cpp
- 2012-12-12 13:36:58 - part of checkin [d52cf3ca74] on branch trunk - Size of the equivalence set : UnionFind. (user: kinaba) [annotate]
To Artifact [c818f654949cbd86]:
- File
lib/typical/unionfind.cpp
- 2015-06-06 12:48:52 - part of checkin [da169a2bbe] on branch trunk - union-find with: semi-compression. (user: kinaba) [annotate]
15 15 { for(int i=0; i<N; ++i) uf[i] = i; }
16 16 int size()
17 17 { return nc; }
18 18 int size(int a)
19 19 { return sz[Find(a)]; }
20 20 int Find(int a)
21 21 { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
22 + // Semi-compression w.o. recursion.
23 + //{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return a; }
22 24 bool Union(int a, int b)
23 25 {
24 26 a = Find(a);
25 27 b = Find(b);
26 28 if( a != b )
27 29 {
28 30 if( sz[a] >= sz[b] ) swap(a, b);