Artifact c818f654949cbd86aa8bba644f5b4e0d60ff1996

• File lib/typical/unionfind.cpp
  • 2015-06-06 12:48:52 - part of checkin [da169a2bbe] on branch trunk - union-find with: semi-compression. (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]); }
		// Semi-compression w.o. recursion.
		//{ while(uf[a] != a) a=uf[a]=uf[uf[a]]; return 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);
		}
};