Artifact 734bdff2cfc3cb9d3b6f9eedd05ff2fdfb0e7edf

• File _lib/typical/unionfind.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/typical/unionfind.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (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 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);
		}
};