#ifndef UFSET_H
#define UFSET_H
class UFset
{
	public:
		UFset(int);
		void Union(int ,int);
		int Find(int);
		int & operator [] (int i){return parent[i];}
		int size(){return length;}
	private:
		int length;//集合的個數
		int * parent;
};
UFset::UFset(int len)
{
	length = len;
	parent = new int [length + 1];
	for(int k = 1; k <= length; k++)
		parent[k] = -1;
}
int UFset::Find(int x)
{
	 int i;
	 for(i = x; parent[i] >= 0; i = parent[i]);//搜索根節點
	 while(i!=x)//路徑壓縮
	 {
		  int tmp = parent[x];
		  parent[x] = i;
		  x = tmp;
	 }
	 return i;
}
void UFset::Union(int x,int y)//合并
{
	int pX = Find(x);
	int pY = Find(y);
	if(pX != pY)
	{
		int tmp = parent[pX] + parent[pY];
		if(parent[pX] > parent[pY])
		{
			parent[pX] = pY;
			parent[pY] = tmp;
		}
		else 
		{
			parent[pY] = pX;
			parent[pX] = tmp;
		}
		length--;
	}
}
#endif