Check-in [d52cf3ca74]
Not logged in
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
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 )