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 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 )