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 11 vector<int> uf, sz;
12 12 int nc;
13 13
14 14 UnionFind(int N): uf(N), sz(N,1), nc(N)
15 15 { for(int i=0; i<N; ++i) uf[i] = i; }
16 16 int size()
17 17 { return nc; }
18 + int size(int a)
19 + { return sz[Find(a)]; }
18 20 int Find(int a)
19 21 { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
20 22 bool Union(int a, int b)
21 23 {
22 24 a = Find(a);
23 25 b = Find(b);
24 26 if( a != b )