#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;}