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