等價類與并查集的原理和應用
??????
并查集主要解決判斷兩個元素是否同屬一個集合，和把兩個不屬同一集合的兩個元素進行合并的問題。
(
想想最小生成樹中的
kruskal
算法
:
關鍵是判別兩個節點是否屬同一連通分量，這里并查集可以以很好的時間復雜度解決它，幾乎是線性時間！！
)
??????
首先要知道關于等價類（就相當于前面說的同屬一個集合）的基本性質。
??????
等價類三大性質：（用Ｘ
o
Ｙ表Ｘ與Ｙ等價）
??????
自反性：如Ｘ
o
Ｘ則Ｘ
o
Ｘ；
??????
對稱性：如Ｘ
o
Ｙ則Ｙ
o
Ｘ；
??????
傳遞性：如Ｘ
o
Ｙ且Ｙ
o
Ｚ則Ｘ
o
Ｚ；
等價類應用：
??????
設初始有一集合
s={0,1,2,3,4,5,6,7,8,9,10,11}
??????
依次讀若干事先定義的等價對
???0o
4,3o
1,6o
10,8o
9,
7o
4,
6o
8,3o
5,2o
11,11o
0.
??? 我們想把每次讀入一個等價對后，把等價集合合并起來。
???
則每讀入一個等價對后的集合狀態是：（用｛｝表示一個等價集合）
初始
?????
{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}
0
o
4
????
{0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}
3
o
1
????
{0,4}, {1,3},{2},{5},{6},{7},{8},{9},{10},{11}
6
o
10??? {
0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}
8
o
9
??? ?
{0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}
7
o
4
????
{0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}
6
o
8
??? ?
{0,4,7},{1,3},{2},{5},{6,8,9,10},{11}
3
o
5
??? ?
{0,4,7},{1,3,5},{2},{6,8,9,10},{11}
2
o
11????{
0,4,7},{1,3,5},{2,11},{6,8,9,10}
11
o
0????{
0,2,4,7,11},{1,3,5},{6,8,9,10}
??????
怎樣來實現這樣的結構呢？
??????
我們可建一個含Ｓ元素個數大小的指針數組
node *seq[N]
。其中每個元素是一個指向其下一個等價元素對應序號節點的頭指針。每讀入一個等價對后，修改鏈表。上例讀完后的表狀態是：
建表算法如下：
void creatlist()
{?int x,y,c;
?node *P;
?scanf("%d",&c);?//讀入等價對數
?for(int i=0;i<c;i++)
?{
??scanf("%d %d",&x,&y);
??P=new node;?
??P->data=y;
??P->next=seq[x];
??seq[x]=P;
??P=new node;?//為什么要兩個節點呢？因為你建了個Ａ的下一等價對Ｂ那么由對稱性，應該再建一個節點表示Ｂ的下一等價對是Ａ。
??P->data=x;
??P->next=seq[y];
??seq[y]=P;
?}//for
}
?
??? 現在我們想把同屬一個等價集合的元素分別輸出出來。有什么辦法呢？
??????
先看圖。Ｓｅｑ［０］它有兩個等價類１１，４。這樣直接輸出０，１１，４。是否可行呢？答案是不行的，你看下４結點還有兩個等價類７，０。當然已知０，４是等價的了，
但７你是忽略的了（因為傳遞性：０，４等價且４，７等價就必然有０，７等價。所以７也應該被輸出）。還有
11
節點下的２你也沒算……
??????
我們可以采用類似ＤＦＳ（深度優先搜索）的策略對每個集合的元素進行遍歷。例如：
開始從０節點搜起，把它下面的兩個直接等價類入棧，然后依次出棧，每次出棧后對出棧元素的直接等價類再進行一次類似的ＤＦＳ，直到包含０節點的等價集合被全部輸出。程序如下：
void display()
{?
?stack<int> S;
?int t;node *p;
?for(int i=0;i<N;i++)
?{
??if(!outed[i])??//是否輸出過的標記
??{
??? cout<<"new class"<<'{';
??? S.push(i);
??? cout<<i<<' ';
??? outed[i]=1;
??? while(!S.empty())
??? {
??? t=S.top();
??? S.pop();
?? ?p=seq[t];
??? while(p!=NULL)
?? ?{
???? if(!outed[p->data])
??? ?{
??? ??cout<<p->data<<' ';
??? ??S.push(p->data);
??? ??outed[p->data]=1;
??? ?}
??? ?p=p->next;
?? ?}//while
???}//while
??? cout<<'}'<<endl;
??}//if
?}//for
}
其實有比這個方便快速的數據結構來實現這個問題，那就是并查集。
并查集對這個問題的處理思想是開始把每一個對象看作是一個單元素集合，然后依次按順序（就是讀入等價對）將屬于同一等價類的元素所在的集合合并。在此過程中將重復地使用一個搜索運算，確定一個元素在哪一個集合中。當讀入一個等價對ＡＢ時，先檢測這兩個等價對是否同屬一個集合，如是，則不用合并。不是，則用個合并算法把這兩個包含ＡＢ的集合合并，使兩個集合的任兩個元素都是等價的（由傳遞性）。
??????
為了方便，我們通常用一個集合的根結點序號來表示這個集合。
來看下具體結構實現：
定義個Ｐａｒｅｎｔ［Ｎ］的數組，作為結構。Ｐａｒｅｎｔ中存的就是序號結點的父親結點的序號，例：如果Ｐａｒｅｎｔ［３］＝４就是說３號結點的雙親是４號結點。如果一個結點的父結點是負數的話，我們就認為它是一個集合的根結點，因為數組中沒有序號是負的。并且用負的絕對值作為這個集合中所含節點個數，如：
parent[6]=-4;
說明６號節點是個集合根結點，這個集合有４個元素。初始時，所有Ｐａｒｅｎｔ賦為
-1
，說明每個結點都是根結點（Ｎ個獨立節點集合），只包含一個元素（就是自己了）。
??????
實現這個數據結構主要有三個函數：如下：
void UFset()??//初始化
{
?for(int i=0;i<N;i++)
??parent[i]=-1;
}
?
int Find(int x)??//返回第Ｘ節點所屬集合的根結點
{
?for(int i=x;parent[i]>=0;i=parent[i]);
?while(i!=x)???//優化方案――壓縮路徑
?{
??int tmp=parent[x];
??parent[x]=i;
???? x=tmp;
?}
?return i;
}
?
void Union(int R1,int R2)??//將兩個不同集合的元素進行合并，使兩個集合中任兩個元素都連通
{
?int tmp=parent[R1]+parent[R2];
?if(parent[R1]>parent[R2])?//優化方案――加權法則
?{
??parent[R1]=R2;
??parent[R2]=tmp;
?}
?else
?{
??parent[R2]=R1;
??parent[R1]=tmp;
?}
}
在Ｆｉｎｄ函數中如果僅僅靠一個循環來直接得到節點的所屬集合根結點的話。通過多次的Ｕｎｉｏｎ操作就會有很多節點在樹的比較深層次中，再Ｆｉｎｄ起來就會很費時。通過加一個Ｗｈｉｌｅ循環（壓縮路徑）每次都把從
i
到集合根結點的路過結點的雙親直接設為集合的根結點。雖然這增加了時間，但以后的Ｆｉｎｄ會快。平均效能而言，這是個高效方法。
兩個集合并時，任一方可做為另一方的孩子。怎樣來處理呢，現在一般采用加權合并，把兩個集合中元素個數少的做為個數多的孩子。有什么優勢呢？直觀上看，可以減少集合樹的深層元素的個數，減少Ｆｉｎｄ時間。
如從０開始到Ｎ不斷合并
i
和
i+1
結點會怎樣呢？
這樣Ｆｉｎｄ任一節點所屬集合的時間復雜度幾乎都是Ｏ
(1)
！！
不用加權規則就會得到
這就是典型的退化樹現象，再Ｆｉｎｄ起來就會很費時（如找Ｎ－１節點看看）。
以下是讀入等價對后的
parent[N]
查找合并過程狀態：
再說一個并查集應用最完美的地方：最小生成樹的
kruskal
算法：
算法基本思想是：
開始把所有節點作為各自的一個單獨集合，以為每次從邊信息中得到一個最短的邊，如果這個邊鄰接了兩個不同集合的節點，就把這兩個節點的所屬集合結合起來，否則繼續搜索。直至所有節點都同屬一個集合，就生成了一個最小生成樹。int kruskal(int parent[],int N)
{
?int i,j,k,x,y;
?int min;
?while(k<=N-1)?//產生Ｎ－１條邊
?{
??min=MAX_INT;
??for(i=1;i<=N;i++)?
???for(j=1;j<=N;j++)
???{
????if(sign[i][j]==0&&i!=j) //sign[N][N]是標志節點是否被訪問過或已被排除……
????{
?????if(arcs[i][j]<min) //arcs[N][N]存放邊的長度
?????{
??????min=arcs[i][j];
??????x=i;
??????y=j;
?????}//if
????}//if
???}//for
??if(Find(parent,x)==Find(parent,y))?//如Ｘ，Ｙ已經屬同一連通分量，則不合并，排除……
???sign[x][y]=1;
??else
???{
??? Union(parent,x,y);
??? Sign[x][y]=1;
?? }
?k++;
?}//while
}