//并查集

#include "iostream.h"
const int DefaultSize = 10;

class UFSets {								//集合中的各個(gè)子集合互不相交。
public:

   UFSets ( int s = DefaultSize );					//構(gòu)造函數(shù)
   ~UFSets ( ) { delete [ ] parent; }					//析構(gòu)函數(shù)
   const UFSets & operator = ( UFSets const & Value );		//重載函數(shù)：集合賦值;省略
   //基本例程
   void Union ( int Root1, int Root2 );					//兩個(gè)子集合合并
   int Find ( int x );							//搜尋集合x的根
   //改進(jìn)例程
   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;								//集合元質(zhì)數(shù)組 (存放各元素的雙親結(jié)點(diǎn)指針)
   int size;									//集合元素的數(shù)目
};

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

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

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

int UFSets::CollapsingFind ( int i ) {
//在包含元素i的樹中搜索根, 并將從i到根的路
//徑上的所有結(jié)點(diǎn)都變成根的子女。				  圖7.11 使用折疊規(guī)則壓縮路徑的示例
   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;
}