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 { for(int i=0; i<N; ++i) uf[i] = i; } 15 { for(int i=0; i<N; ++i) uf[i] = i; }
16 int size() 16 int size()
17 { return nc; } 17 { return nc; }
18 int size(int a) 18 int size(int a)
19 { return sz[Find(a)]; } 19 { return sz[Find(a)]; }
20 int Find(int a) 20 int Find(int a)
21 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } 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 bool Union(int a, int b) 24 bool Union(int a, int b)
23 { 25 {
24 a = Find(a); 26 a = Find(a);
25 b = Find(b); 27 b = Find(b);
26 if( a != b ) 28 if( a != b )
27 { 29 {
28 if( sz[a] >= sz[b] ) swap(a, b); 30 if( sz[a] >= sz[b] ) swap(a, b);