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