Artifact 12244591e3a7308ea9d73326e9cdd03aab9e1376

• 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]

//-------------------------------------------------------------
// Union-Find
//   Balancing + Path-Compression : O(invAckermann)
//
// Verified by
//   - SRM Member Pilot 2 Div1 LV2
//-------------------------------------------------------------

struct UnionFind
{
	vector<int> uf, sz;
	int nc;

	UnionFind(int N): uf(N), sz(N,1), nc(N)
		{ for(int i=0; i<N; ++i) uf[i] = i; }
	int size()
		{ return nc; }
	int size(int a)
		{ return sz[Find(a)]; }
	int Find(int a)
		{ return uf[a]==a ? a : uf[a]=Find(uf[a]); }
	bool Union(int a, int b)
		{
			a = Find(a);
			b = Find(b);
			if( a != b )
			{
				if( sz[a] >= sz[b] ) swap(a, b);
				uf[a] = b;
				sz[b] += sz[a];
				--nc;
			}
			return (a!=b);
		}
};