The Fourth Dimension Space

并查集學習小節(POJ版)

什么是并查集呢，我相信大家都已經很熟悉了，在這里我就不再贅述。寫這篇文章的主要目的不是新手教學，而是為了借POJ上相關的題目，全面的總結一下并查集問題和它的各個變種。

POJ 1611 The Suspects
題目大意:有n個學生（標號為0 to n-1),m個學生社團，給出每個社團里所有學生的標號，并假設0號學生患有SARS（社團里只要用一個學生患病，則整個社團里的學生都會被隔離），問最后一共會有多少學生被隔離？
這是一個最基礎的并查集的應用，掃描每一個社團，只要兩個學生出現在同一個社團，則將這兩個集合合并起來，最后輸出0號點所在集合的rank值集合（rank值記錄這個集合中的元素個數并用一個flag值跟蹤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.然后是壓縮路徑時候的偏移量改變
個人認為，這個主要是解決集合合并時候產生的“殘余問題”，因為在合并集合的時候只是考慮了集合的偏移量，至于它下面的元素一概不管。一個壓縮路徑既分離了父子元素的偏移量，又使得子元素直接指向集合元素。

總而言之，并查集的操作就是不斷地維護者各個集合中，每個元素身上對集合元素的偏移關系。從而確定他們是否具有同性戀。
在這個題中，假設是不存在同性戀的，所以只有找到矛盾才輸出 有同性戀。

POJ 1182 食物鏈 
中文題，讓你輸出假話的個數。其實這道題是上一道題的擴展，如果把上一道題也想成是食物鏈的話，就是1吃2，2吃1.
而這里是三個動物，所以同樣是維護一個偏移量，只不過多了一位罷了。
程序的過程實質上就是在維護并查集，判斷是否是假話是在維護的過程中進行的，只能算是附屬品吧。

 這里將兩個集合并起來并將所掛集合偏移量指向：
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行，每行有一條指令。指令有兩種格式：

1. M i j ：i和j是兩個整數（1<=i , j<=30000），表示指令涉及的戰艦編號。該指令是萊因哈特竊聽到的楊威利發布的艦隊調動指令，并且保證第i號戰艦與第j號戰艦不在同一列。

2. 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://www.shnenglu.com/abilitytao/archive/2009/10/18/98899.html

posted on 2009-10-18 21:31 abilitytao 閱讀(3170) 評論(5)  編輯 收藏 引用