Differences From Artifact [734bdff2cfc3cb9d]:
- File
_lib/typical/unionfind.cpp
- 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
- File
lib/typical/unionfind.cpp
- 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]
To 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]
11 vector<int> uf, sz; 11 vector<int> uf, sz;
12 int nc; 12 int nc;
13 13
14 UnionFind(int N): uf(N), sz(N,1), nc(N) 14 UnionFind(int N): uf(N), sz(N,1), nc(N)
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)
> 19 { return sz[Find(a)]; }
18 int Find(int a) 20 int Find(int a)
19 { return uf[a]==a ? a : uf[a]=Find(uf[a]); } 21 { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
20 bool Union(int a, int b) 22 bool Union(int a, int b)
21 { 23 {
22 a = Find(a); 24 a = Find(a);
23 b = Find(b); 25 b = Find(b);
24 if( a != b ) 26 if( a != b )