#pragma once
#include <map>
using namespace std;

template<class T>
class CUnionSet
{
public:
	CUnionSet(): size(0) {}
	void MakeSet(T k);
	void JoinSet(T x, T y);		
	bool Together(T x, T y);	
	int  SetSize(T x);			//包含了x的這個部分所含有元素的個數
	int  Size();				//該并查集分成了幾個部分
	void Clear();
protected:
	map<T, T> father;
	map<T, int> rank;
private:	    
	T FindRoot(T x);
	int size;
};

template<class T>
void CUnionSet<T>::Clear()
{
	father.clear();
	rank.clear();
	size = 0;
}

template<class T>
void CUnionSet<T>::MakeSet(T k)
{
	if(rank[k] == 1)
		return;
	father[k] = k;
	rank[k] = 1;
	size++;
}

template<class T>
void CUnionSet<T>::JoinSet(T x, T y)
{
	//必須保證x, y都已經存在
	T XX = FindRoot(x);
	T YY = FindRoot(y);

	if(XX == YY)
		return;

	//we need not update the value of rank[yy] or rand[xx];
	if(rank[XX] > rank[YY])	
	{
		father[YY] = XX;
		rank[XX] += rank[YY];		
	}
	else
	{
		father[XX] = YY;
		rank[YY] += rank[XX];		
	}
	size--;
}

template<class T>
T CUnionSet<T>::FindRoot(T x )
{
	/*
		可能會存在異常。map[x]，假如x本身就不存在，它會返回0值，
		但是這個0值不能和已經存在的0值區分開
	*/
	while(x != father[x])
		 x = father[x];
	return x;	
}

template<class T>
int CUnionSet<T>::Size()
{		 
	return size;
}

template<class T>
bool CUnionSet<T>::Together(T x, T y)
{
	return FindRoot(x) == FindRoot(y);
}

template<class T>
int CUnionSet<T>::SetSize(T x)
{
	return rank[FindRoot(x)];
}