并查集的初級(jí)應(yīng)用及進(jìn)階
一、精華
精華提煉1：
內(nèi)容：并查集就是樹的孩子表示法的應(yīng)用。
解釋：對(duì)于下圖所示樹，它的孩子表示法為：
belg[5]=2, belg[6]=2, belg[7]=2;
belg[2]=1, belg[3]=1, belg[4]=1;
belg[1]=1(也可以=-1,只要能夠識(shí)別它是根就可以)
精華提煉2：
內(nèi)容：并查集的孩子父親表示法中，每個(gè)節(jié)點(diǎn)與其父親節(jié)點(diǎn)可以添加一個(gè)關(guān)系屬性(必須具有可傳遞性)。
解釋：比如，節(jié)點(diǎn)表示一個(gè)人，關(guān)系屬性為一個(gè)人的性別。我們先用上圖來解釋這個(gè)關(guān)系屬性的應(yīng)用，在后文具體展開。我們可以這樣定義，如果節(jié)點(diǎn)i和其父節(jié)點(diǎn)j性別相同（belg[i]=j），則kind[i]=false, 反之，kind[i]=true，那么如果我們知道kind[5]=true，kind[2]=false，那么5和2的父節(jié)點(diǎn)1的關(guān)系為kind[5]^kind[2]=true，即他們性別不同。
二、基礎(chǔ)
基礎(chǔ)1：集合表示
根據(jù)精華提煉1，我們把一顆樹的節(jié)點(diǎn)集合看成以根節(jié)點(diǎn)命名的集合，那么上面的集合我們可以認(rèn)為是集合1。
下圖共有兩個(gè)集合，分別為集合1，集合2。
基礎(chǔ)2：元素關(guān)系
如何判斷元素關(guān)系呢？其實(shí)，我們只需找出元素對(duì)應(yīng)的集合名稱，然后判斷名稱是否相同即可。尋找集合名稱代碼如下：
int Find(int x)
{
while ( belg[x]!=x )
x = belg[x];
return x;
}
例如：對(duì)于基礎(chǔ)1中左圖,有belg[5]=2，belg[2]=2。那么5屬于集合2。
現(xiàn)在我們已經(jīng)解決了元素關(guān)系問題。
基礎(chǔ)3：集合合并
集合如何合并呢？基礎(chǔ)2中，我們已經(jīng)可以找到元素對(duì)應(yīng)集合的名稱（即根節(jié)點(diǎn)標(biāo)號(hào)），如果元素u、v（u、v不在同一集合）對(duì)應(yīng)的集合名稱為_u、_v，那么語句belg[_u]=_v什么意思呢？想到了吧？就是把集合_u與集合_v合并，并且以_v命名。
至此，通過基礎(chǔ)部分我們知道了什么是并查集，通過精華提煉部分，我們知道了并查集的高級(jí)應(yīng)用（精華提煉2）。
三、優(yōu)化
雖然我們已經(jīng)知道了基礎(chǔ)的并查集，但是大家有沒有想過簡(jiǎn)單用上面介紹的集合合并可能造成集合（樹）的退化。比如對(duì)只有一個(gè)元素的集合1到集合n進(jìn)行下述操作：把集合1合并到集合2，把集合2合并到集合3，…… 把集合n-1合并到集合n，那么生成一個(gè)含有n各元素的集合n，它的結(jié)構(gòu)如下：
那么，每次判斷n所屬集合都要n次操作，即復(fù)雜度為O(n)，這個(gè)耗費(fèi)是不是必須的呢？其實(shí)不然。
優(yōu)化1：路徑壓縮
對(duì)于上圖退化的集合，它的表示是這樣的：belg[n]=n-1， belg[n-1]=n-2， …… belg[2]=1， belg[1]=1；
既然上面元素都屬于集合1，那么我們是不是可以這樣做呢？belg[n]=1，belg[n-1]=1，……belg[2]=1，belg[1]=1；即把查找n所屬集合時(shí)形成的路徑上的點(diǎn)直接連到根節(jié)點(diǎn)上。可以的，因?yàn)檫@樣操作只改變集合樹的結(jié)構(gòu)，并沒有改變這個(gè)集合的元素。
關(guān)于路徑壓縮，可以在查找過程中實(shí)現(xiàn)，那么對(duì)于上述退化樹，查找n第一次要n次操作，以后就只需一次操作。實(shí)現(xiàn)如下：
版本一：（遞歸）
int Find(int x)
{
return x==belg[x]?x:(belg[x]=Find(belg[x]));
}
代碼很短，遞歸次數(shù)多時(shí)，不建議使用。
版本二：（迭代）
int Find(int x)
{
int _b, _x = x;
while ( belg[_x]!=_x )
_x = belg[_x];
while ( belg[x]!=x )
{
_b = belg[x];
belg[x] = _x;
x = _b;
}
return _x;
}
代碼長(zhǎng)點(diǎn)，但是少了遞歸過程，效率高點(diǎn)。
優(yōu)化2：優(yōu)化合并
合理的安排合并方式，可以防止退化，例如對(duì)于上述退化的例子，我們把元素少的集合合并到元素多的集合上。即集合2合并到集合1，集合3合并到集合1，……集合n合并到集合1，那么產(chǎn)生的樹結(jié)構(gòu)為：
不過這個(gè)優(yōu)化代價(jià)也很大的，因?yàn)橐獙?duì)開一個(gè)整型數(shù)組來記錄集合元素個(gè)數(shù)，然后，再集合i和集合j合并時(shí)，通過判斷集合中元素個(gè)數(shù)來實(shí)現(xiàn)合并：
int Union(int i, int j)
{
if ( sum[i]>sum[j] )
belg[j] = i;
else
belg[i] = j;
}
細(xì)心的讀者，可能想到這個(gè)優(yōu)化并不能完全避免集合退化，是的，所以我認(rèn)為不必開辟數(shù)組浪費(fèi)空間進(jìn)行這個(gè)優(yōu)化，完全可以隨機(jī)法來由優(yōu)化，比如：
int Union(int i, int j)
{
if ( rand()&1 )
belg[j] = i;
else
belg[i] = j;
}
通過隨機(jī)值的奇偶性來決定怎么合并，平均效果是很好的。
上面詳細(xì)講了這么多理論性的東西，下面開始介紹應(yīng)用：
四、應(yīng)用
基礎(chǔ)應(yīng)用：
題目：
有n個(gè)人（1..n），如果i和j是親戚，j和k是親戚，那么j和k也是親戚，題目給定n各人的m對(duì)親戚關(guān)系，然后提出q各問題，問你某兩個(gè)人是不是親戚。
解答：
并查集簡(jiǎn)單應(yīng)用，代碼如下：
#include <iostream>
using namespace std;
const int MAXN = 1010;
int belg[MAXN];
int main()
{
int i, u, v, n, m, q;
scanf("%d", &n);
for ( i=1; i<=n; belg[i]=i,++i )
;
scanf("%d", &m);
for ( i=1; i<=m; ++i )
{
scanf("%d%d", &u, &v);
u = Find(u);
v = Find(v);
if ( u!=v )
Union(u,v);
}
scanf("%d", &q);
for ( i=1; i<=q; ++i )
{
scanf("%d%d", &u, &v);
u = Find(u);
v = Find(v);
printf("%s\n", (u==v?"YES":"NO"));
}
return 0;
}
其中Find函數(shù)和Union函數(shù)參見上面的介紹。
高級(jí)應(yīng)用：
題目：（HDU1829）
有n各小動(dòng)物，它們只有異性之間才配對(duì)，同性之間不會(huì)配對(duì)。給定m對(duì)配對(duì)關(guān)系，問你是否能通過分配性別給n各小動(dòng)物，使這m各配對(duì)關(guān)系成立，即不會(huì)出現(xiàn)同性之間配對(duì)。
解答：
這里我們使用在精華提煉二中提到的思路。
首先，我們必須明確兩點(diǎn)：1.這里的屬于同一個(gè)集合的元素表示他們的關(guān)系已經(jīng)確定，比如元素i和元素j屬于同一個(gè)集合，那么他們要么同性，要么異性，關(guān)系時(shí)確定的。2.同一個(gè)集合的樹表示中，節(jié)點(diǎn)i和它的父親節(jié)點(diǎn)j關(guān)系存儲(chǔ)在kind[i]中。
同時(shí)，我們約定，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j性別相同，則關(guān)系為false，否則關(guān)系為true。根節(jié)點(diǎn)root滿足kind[root]=false，因?yàn)樽约焊约盒詣e肯定相同（當(dāng)然不包括人妖了哈^-^）。
關(guān)系的運(yùn)算我們可以通過異或（提示1）來實(shí)現(xiàn)，如果i和j關(guān)系為r1，i和k關(guān)系為r2，那么j和k關(guān)系為r1^r2。
上面的分析已經(jīng)足夠我們處理這個(gè)題目了。下面給出代碼：
#include <iostream>
using namespace std;
const int MAXN = 2010;
int belg[MAXN];
bool kind[MAXN];
int Find(int x, bool &s);
int main()
{
int i, k, n, m;
int u, v, _u, _v, cas;
bool flag, su, sv;
scanf("%d", &cas);
for ( k=1; k<=cas; ++k )
{
scanf("%d%d", &n, &m);
for ( i=1; i<=n; ++i )
{
belg[i] = i;
kind[i] = false;
}
for ( i=1,flag=true; i<=m; ++i )
{
scanf("%d%d", &u, &v);
if ( flag )
{
_u = Find(u,su=false);
_v = Find(v,sv=false);
if ( _u==_v )
{
flag = su^sv;
}
else
{
belg[_u] = _v;
kind[_u] = !(su^sv);
}
}
}
printf("Scenario #%d:\n", k);
if ( flag )
{
printf("No suspicious bugs found!\n\n");
}
else
{
printf("Suspicious bugs found!\n\n");
}
}
return 0;
}
int Find(int x, bool &s)
{
int h;
if ( belg[x]==x )
{
h = x; s = false;
}
else
{
h = Find(belg[x],s);
belg[x] = h;
s = kind[x]^s;
kind[x] = s;
}
return h;
}
由于上述Find函數(shù)使用了遞歸所以比較耗時(shí)（1609毫秒，132KB），可以改為如下的迭代形式（671毫秒，0KB）：
int Find(int x, bool &s)
{
int _x, h = x;
bool s1, s2;
while ( belg[h]!=h )
{
s = s^kind[h];
h = belg[h];
}
s1 = s;
while ( belg[x]!=x )
{
_x = belg[x];
belg[x] = h;
s2 = kind[x];
kind[x] = s1;
s1 = s1^s2;
x = _x;
}
return h;
}
提示1.異或：i和j異或就是：如果i和j相同則為false，否則為true，比如i=true，j=false，則i異或j為true。i=false，j=false，則i異或j為false。