#include "iostream.h"
const int DefaultSize = 100;
class UFSets {								//集合中的各個子集合互不相交。
public:
   UFSets ( int s = DefaultSize );					//構造函數
   ~UFSets ( ) { delete [ ] parent; }					//析構函數
   const UFSets & operator = ( UFSets const & Value );		//重載函數：集合賦值;省略
   //基本例程
   void Union ( int Root1, int Root2 );					//兩個子集合合并
   int Find ( int x );							//搜尋集合x的根
   //改進例程
   void UnionByHeight ( int Root1, int Root2 );			//壓縮高度的合并算法,省略
   void WeightedUnion ( int Root1, int Root2 );
   int CollapsingFind ( int i );
   friend ostream& operator <<(ostream& strm, UFSets& a);
private:
   int *parent;								//集合元質數組 (存放各元素的雙親結點指針)
   int size;									//集合元素的數目
};

UFSets::UFSets ( int s ) {
//構造函數：s是集合元素個數。雙親指針數組的范圍為parent[0]～parent[size]。
   size = s;									//集合元素個數
   parent = new int [size+1];						//創建雙親指針數組
   for ( int i=0; i<=size; i++ ) parent[i] = -1;				//每一個自成一個單元素集合
}

int UFSets::Find ( int x ) {
//函數搜索并返回包含元素x的樹的根。
   if ( parent[x] < 0 ) return x;						//x是根時直接返回x
   else return Find ( parent[x] );						//否則, 遞歸找x的雙親的根
}

void UFSets::Union ( int Root1, int Root2 ) {
//函數求兩個不相交集合的并。要求Root1與Root2是不同的, 且表示了子集合的名字。因為union是C++
//的關鍵碼, 為不致混亂, 可使用Set_Union來命名函數。
   parent[Root2] = Root1;				//將根Root2連接到另一根Root1下面
}
void UFSets::WeightedUnion ( int Root1, int Root2 ) {
//使用結點個數探查方法求兩個UF sets型集合的并。要求Root1與Root2是不同的, 且表示了子集合的名字。	
   Root1=CollapsingFind ( Root1 );
   Root2=CollapsingFind ( Root2 );
   int temp = parent[Root1] + parent[Root2];
   if ( parent[Root2] < parent[Root1] )					//以Root2為根的樹結點多一些
     { parent[Root1] = Root2;  parent[Root2] = temp; }		//讓Root1直接接在Root2下面
   else { parent[Root2] = Root1;  parent[Root1] = temp; }		//讓Root1成為新的根
}

int UFSets::CollapsingFind ( int i ) {
//在包含元素i的樹中搜索根, 并將從i到根的路
//徑上的所有結點都變成根的子女。				  圖7.11 使用折疊規則壓縮路徑的示例
   for ( int j=i; parent[j]>=0; j=parent[j]);		//搜索根j
   while ( i != j ) {						//向上逐次壓縮
	 int temp = parent[i];
	 parent[i] = j;  i = temp;
  }
   return j;							//返回根
}
ostream& operator <<(ostream& strm, UFSets& a)
{
  for (int i=0;i<=a.size;i++)
  { 
    strm<<"Father of "<<i<<" is "<<a.parent[i]<<endl;
  }
  strm<<endl;
  return strm;
}