什么是并查集呢，我相信大家都已經很熟悉了，在這里我就不再贅述。寫這篇文章的主要目的不是新手教學，而是為了借POJ上相關的題目，全面的總結一下并查集問題和它的各個變種。
POJ 1611 The Suspects
題目大意:有n個學生（標號為0 to n-1),m個學生社團，給出每個社團里所有學生的標號，并假設0號學生患有SARS（社團里只要用一個學生患病，則整個社團里的學生都會被隔離），問最后一共會有多少學生被隔離？
這是一個最基礎的并查集的應用，掃描每一個社團，只要兩個學生出現在同一個社團，則將這兩個集合合并起來，最后輸出0號點所在集合的rank值集合（rank值記錄這個集合中的元素個數并用一個flag值跟蹤0號元素所在集合標號）即可。
這是并查集問題的第一種應用：集合合并，判斷兩點是不是在同一個集合，求某一個集合上的元素個數等。
#include<stdio.h>
#define MAX 30000
int f[MAX];//這里的1001只是一個示意性的數字 代表初始狀態下的分支數目
int r[MAX];
int flag;
//由于不知道應該將子樹掛到那個集合上面去，故需要一個準則，這里的準則是將子樹掛到
//r值大的集合上面去,初始狀態下r數組的值均為一，代表每個分支下只有一個數字
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}//查找函數，并壓縮路徑
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
if(a==flag)
flag=b;
}
else
{
f[b]=a;
r[a]+=r[b];
if(b==flag)
flag=a;
}
return 1;
}//合并函數，如果屬于同一分支則返回0，成功合并返回1
int main()
{
int n,m;
int i,j;
int num;
int maxnum=0;
while(scanf("%d%d",&n,&m))
{
flag=0;
maxnum=0;
int temp1,temp2;
if(n==0&&m==0)
break;
for(i=0;i<n;i++)
{
f[i]=i;
r[i]=1;
}
for(j=1;j<=m;j++)
{
scanf("%d",&num);
for(i=0;i<num;i++)
{
if(i==0)
scanf("%d",&temp1);
else
{
scanf("%d",&temp2);
Union(temp1,temp2);
}
}
}
printf("%d\n",r[flag]);
}
return 0;
}
POJ 2492 A Bug's Life
個人認為它是初級并查集問題的一個升級。同時這個題讓我看到了食物鏈的影子。。。
題目的大意是給出n只bug和m次觀察到的性行為，并以此為依據判斷兩只bugs是不是有同性戀行為(gay)。
比如3只bug
1 2有性行為
2 3有性行為
1 3有性行為
---->>>>>首先1,2是異性。
---->>>>>然后2,3是異性。
可以推出1,3是異性。
但是1，3有性行為，所以可以判斷出有一定有同性戀。
剝離這個題目所賦予的外殼，我們抽出這個問題的本質：并查集！
其實，這里最重要的是去維護每一個點到集合頂點的偏移量。（注意：下面生造了一個詞 所謂集合元素 比如說f[i]=i,那么i就是集合元素，集合偏移量就是集合元素的偏移量）
初始狀態下，應該是
i號點掛在i號集合下面
我們考慮一般情況：假設合并的過程已經進行了一部分 ，這樣每一個集合下面都有元素，且各自對于頂點的偏移量都算出來了；
現在在a集合中的元素x和b集合中的元素y進行合并。此時有兩中情況改變偏移量；
1.首先是集合的合并，如果要將a,b集合合并，又要保證x,y數字的kind不相同，比如說把b集合掛到a集合下面去。
代表集合的那個元素，他的偏移量永遠是0，所以b要改變偏移量，使得b里面的y在進行變換后要和x相異。
如果 kind[x]=0;kind[y]=0;那么y對應的那個代表集合的元素的偏移量必須變成1，因為只有這樣才能使得合并后，x,y有不同的kind;
如果 kind[x]=0,kind[y]=1;y對應代表集合的元素偏移量是0，所以對應集合偏移量還是0；
類推 kind[x]=1,kind[y]=0,同上,0；
kind[x]=1,kind[y]=1,y集合偏移量應該變為1；
綜上 可以得到一個同或的關系。
用等式 kind
[a
]=(kind
[x
]+kind
[y
]+1)%2;恰好滿足要求.
2.然后是壓縮路徑時候的偏移量改變
個人認為，這個主要是解決集合合并時候產生的“殘余問題”，因為在合并集合的時候只是考慮了集合的偏移量，至于它下面的元素一概不管。一個壓縮路徑既分離了父子元素的偏移量，又使得子元素直接指向集合元素。
總而言之，并查集的操作就是不斷地維護者各個集合中，每個元素身上對集合元素的偏移關系。從而確定他們是否具有同性戀。
在這個題中，假設是不存在同性戀的，所以只有找到矛盾才輸出 有同性戀。
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 2001
int f[MAX];
int kind[MAX];
int n,m;
int testcase;
void init()
{
int i;
for(i=1;i<=n;i++)
{
f[i]=i;
kind[i]=0;
}
}
int Find(int n)
{
if(f[n]==n)
return n;
int t=Find(f[n]);
kind[n]=(kind[n]+kind[f[n]])%2;
f[n]=t;
return f[n];
}
int Union(int x,int y)
{
int a=Find(x);
int b=Find(y);
if(a==b)
{
if(kind[x]==kind[y])
return 1;//1代表有同性戀情況
}
else
{
f[a]=b;
kind[a]=(kind[x]+kind[y]+1)%2;
}
return 0;
}
int main()
{
scanf("%d",&testcase);
int i,j;
int a,b;
int flag;
for(i=1;i<=testcase;i++)
{
flag=0;
scanf("%d%d",&n,&m);
init();
for(j=1;j<=m;j++)
{
scanf("%d%d",&a,&b);
if(Union(a,b))
{
flag=1;
}
}
if(flag==1)
printf("Scenario #%d:\nSuspicious bugs found!\n\n",i);
else
printf("Scenario #%d:\nNo suspicious bugs found!\n\n",i);
}
return 0;
}
POJ 1182 食物鏈
中文題，讓你輸出假話的個數。其實這道題是上一道題的擴展，如果把上一道題也想成是食物鏈的話，就是1吃2，2吃1.
而這里是三個動物，所以同樣是維護一個偏移量，只不過多了一位罷了。
程序的過程實質上就是在維護并查集，判斷是否是假話是在維護的過程中進行的，只能算是附屬品吧。
#include<iostream>
using namespace std;
#define MAX 50005
int f[MAX];
int kind[MAX];
int n,m;
void init()
{
int i;
for(i=1;i<=n;i++)
{
f[i]=i;
kind[i]=0;
}
}
int Find(int n)
{
if(f[n]==n)
return n;
int t=Find(f[n]);
kind[n]=(kind[n]+kind[f[n]])%3;
f[n]=t;
return f[n];
}
bool Union(int x,int y,int c)
{
if(x>n||y>n)
return 1;
int a=Find(x);
int b=Find(y);
if(c==1)
{
if(a==b)
{
if(kind[x]!=kind[y])
return true;
}
else if(a!=b)
{
f[b]=a;
kind[b]=(kind[x]-kind[y]+3)%3;
}
}
else
{
if(x==y)
return true;
if(a==b)
{
if((kind[x]+1)%3!=kind[y])
return true;
}
else if(a!=b)
{
f[b]=a;
kind[b]=(kind[x]-kind[y]+4)%3;
}
}
return false;
}
int main()
{
int i,j;
int a,b,c;
int sum=0;
scanf("%d%d",&n,&m);
init();
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&c,&a,&b);
if(Union(a,b,c))
sum++;
}
printf("%d\n",sum);
return 0;
}
這里將兩個集合并起來并將所掛集合偏移量指向：
kind[b]
=(kind[x]-kind[y]+4)%3;
想想上一題是不是也很類似呢
其實上一題的公式也可以改成
kind[b]=(kind[x]-kind[y]+3)%2;
不管是幾個動物循環，都能得到類似的結論，所以以后碰到4，5，6，7。。。個動物的食物鏈，你應該也會做了吧？^_^
POJ 1988 Cube Stacking
這道題更有意思了，說它開辟了并查集問題的新局面并不為過；上面2道題，研究的主要是到集合元素的偏移量，而這道題要求的是一個“邏輯上”到達集合元素的距離！集合合并的時候同樣只修改被掛集合元素的距離值，殘余部分留給壓縮路徑來處理.
如果理解了上面的問題，這個問題就很好理解了。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAX 30000
int f[MAX+1];
int r[MAX+1];
int above[MAX+1];
void init()
{
int i;
for(i=1;i<=MAX;i++)
{
above[i]=0;
f[i]=i;
r[i]=1;
}
}
int realfather;
int find(int n)
{
int t;
if(f[n]==n)
{
realfather=n;
return n;
}
else
{
t=find(f[n]);
if(f[n]!=realfather)
above[n]+=(above[f[n]]);
f[n]=t;
}
return f[n];
}//查找函數，并壓縮路徑
void Union(int x,int y)
{
int a=find(x);
int b=find(y);
f[b]=a;
above[b]+=r[a];
r[a]+=r[b];
}//合并函數，如果屬于同一分支則返回0，成功合并返回1
int main()
{
int p;
int i;
init();
char order;
int a,b;
scanf("%d",&p);
for(i=1;i<=p;i++)
{
cin.ignore();
scanf("%c",&order);
if(order=='M')
{
scanf("%d%d",&a,&b);
Union(a,b);
}
else if(order=='C')
{
scanf("%d",&a);
printf("%d\n",r[find(a)]-above[a]-1);
}
}
return 0;
}
銀河英雄傳說 NOI 2002
說道并查集，還有一道非常經典的題目 還有那個“著名”的楊威利元帥，呵呵。這題附上原題，有了上面的講解，相信你能很快找到解法^_^
銀河英雄傳說
【問題描述】
公元五八○一年，地球居民遷移至金牛座α第二行星，在那里發表銀河聯邦創立宣言，同年改元為宇宙歷元年，并開始向銀河系深處拓展。
宇宙歷七九九年，銀河系的兩大軍事集團在巴米利恩星域爆發戰爭。泰山壓頂集團派宇宙艦隊司令萊因哈特率領十萬余艘戰艦出征，氣吞山河集團點名將楊威利組織麾下三萬艘戰艦迎敵。
楊威利擅長排兵布陣，巧妙運用各種戰術屢次以少勝多，難免恣生驕氣。在這次決戰中，他將巴米利恩星域戰場劃分成30000列，每列依次編號為1, 2, …, 30000。之后，他把自己的戰艦也依次編號為1, 2, …, 30000，讓第i號戰艦處于第i列(i = 1, 2, …, 30000)，形成“一字長蛇陣”，誘敵深入。這是初始陣形。當進犯之敵到達時，楊威利會多次發布合并指令，將大部分戰艦集中在某幾列上，實施密集攻擊。合并指令為M i j，含義為讓第i號戰艦所在的整個戰艦隊列，作為一個整體（頭在前尾在后）接至第j號戰艦所在的戰艦隊列的尾部。顯然戰艦隊列是由處于同一列的一個或多個戰艦組成的。合并指令的執行結果會使隊列增大。
然而，老謀深算的萊因哈特早已在戰略上取得了主動。在交戰中，他可以通過龐大的情報網絡隨時監聽楊威利的艦隊調動指令。
在楊威利發布指令調動艦隊的同時，萊因哈特為了及時了解當前楊威利的戰艦分布情況，也會發出一些詢問指令：C i j。該指令意思是，詢問電腦，楊威利的第i號戰艦與第j號戰艦當前是否在同一列中，如果在同一列中，那么它們之間布置有多少戰艦。
作為一個資深的高級程序設計員，你被要求編寫程序分析楊威利的指令，以及回答萊因哈特的詢問。
最終的決戰已經展開，銀河的歷史又翻過了一頁……
【輸入文件】
輸入文件galaxy.in的第一行有一個整數T（1<=T<=500,000），表示總共有T條指令。
以下有T行，每行有一條指令。指令有兩種格式：
-
M i j ：i和j是兩個整數（1<=i , j<=30000），表示指令涉及的戰艦編號。該指令是萊因哈特竊聽到的楊威利發布的艦隊調動指令，并且保證第i號戰艦與第j號戰艦不在同一列。
-
C i j ：i和j是兩個整數（1<=i , j<=30000），表示指令涉及的戰艦編號。該指令是萊因哈特發布的詢問指令。
【輸出文件】
輸出文件為galaxy.out。你的程序應當依次對輸入的每一條指令進行分析和處理：
如果是楊威利發布的艦隊調動指令，則表示艦隊排列發生了變化，你的程序要注意到這一點，但是不要輸出任何信息；
如果是萊因哈特發布的詢問指令，你的程序要輸出一行，僅包含一個整數，表示在同一列上，第i號戰艦與第j號戰艦之間布置的戰艦數目。如果第i號戰艦與第j號戰艦當前不在同一列上，則輸出-1。
【樣例輸入】
4
M 2 3
C 1 2
M 2 4
C 4 2
【樣例輸出】
-1
1
【樣例說明】
戰艦位置圖：表格中阿拉伯數字表示戰艦編號
|
|
第一列
|
第二列
|
第三列
|
第四列
|
……
|
|
初始時
|
1
|
2
|
3
|
4
|
……
|
|
M 2 3
|
1
|
|
3
2
|
4
|
……
|
|
C 1 2
|
1號戰艦與2號戰艦不在同一列，因此輸出-1
|
|
M 2 4
|
1
|
|
|
4
3
2
|
……
|
|
C 4 2
|
4號戰艦與2號戰艦之間僅布置了一艘戰艦，編號為3，輸出1
|
不知道并查集問題還有沒有什么別的變種呢？除了維護偏移量和到頂點的距離，還有沒有可能是別的情況呢？比如說。。。。。。如果你有更好的想法，歡迎和我交流。
文章由abilitytao原創
轉載請注明出處：http://m.shnenglu.com/abilitytao/archive/2009/10/18/98899.html