Overview
| SHA1 Hash: | d52cf3ca74b8b3d0e6103100eea4ee6421c9cdfe |
|---|---|
| Date: | 2012-12-12 13:36:58 |
| User: | kinaba |
| Comment: | Size of the equivalence set : UnionFind. |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Modified lib/typical/unionfind.cpp from [734bdff2cfc3cb9d] to [12244591e3a7308e].
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 )