青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

并查集學習小節(POJ版)

什么是并查集呢,我相信大家都已經很熟悉了,在這里我就不再贅述。寫這篇文章的主要目的不是新手教學,而是為了借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的第一行有一個整數T1<=T<=500,000),表示總共有T條指令。

以下有T行,每行有一條指令。指令有兩種格式:

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

  2. C i j ij是兩個整數(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 閱讀(3189) 評論(5)  編輯 收藏 引用

評論

# re: 并查集學習小節(POJ版) 2009-11-12 08:54 ljf

cube stacking 那個find中沒必要用那個realfather吧?
因為above[realfather] = 0
加不加那個判斷都無所謂,是不是?  回復  更多評論   

# re: 并查集學習小節(POJ版) 2010-05-14 16:43 lqq

第一題,那個壓縮路徑的算法好像少了一點東西  回復  更多評論   

# re: 并查集學習小節(POJ版) 2010-07-18 12:07 簡單就好

Union函數不用返回值,可定義為void型  回復  更多評論   

# re: 并查集學習小節(POJ版) 2010-07-18 22:04 abilitytao

@簡單就好
返回值為1代表合并成功,返回值為0代表合并不成功。  回復  更多評論   

# re: 并查集學習小節(POJ版) 2015-07-19 09:01 謝謝

xiexie  回復  更多評論   

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            欧美国产欧美综合 | 欧美成人乱码一区二区三区| 国产精品一区二区在线观看网站 | 亚洲国产99| 欧美黑人国产人伦爽爽爽| 久久久久九九九九| 在线电影欧美日韩一区二区私密| 裸体素人女欧美日韩| 久久夜色精品| 一本色道久久综合亚洲精品不卡| 一本色道久久综合亚洲精品不卡| 国产精品久久久久久五月尺| 午夜久久tv| 久久久噜噜噜久久久| 亚洲麻豆av| 亚洲综合视频一区| 在线观看日韩av电影| 亚洲精品男同| 国产精品国产三级欧美二区| 久久gogo国模裸体人体| 久热精品在线视频| 亚洲伊人第一页| 久久精品男女| 在线中文字幕不卡| 久久aⅴ国产紧身牛仔裤| 亚洲人成欧美中文字幕| 亚洲少妇最新在线视频| 一区二区自拍| 一区二区三区毛片| 亚洲国产欧美精品| 亚洲欧美亚洲| 亚洲视频在线观看网站| 久久久久网址| 欧美一区二区三区视频免费播放| 美女主播精品视频一二三四| 亚洲欧美视频在线| 欧美黑人在线播放| 另类欧美日韩国产在线| 欧美色图五月天| 亚洲丰满少妇videoshd| 国产日韩av高清| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 一本到高清视频免费精品| 国产毛片精品国产一区二区三区| 欧美99在线视频观看| 国产精品你懂得| 91久久精品国产91久久性色tv| 国产精品欧美日韩| 99视频精品| 亚洲精品1区| 久久精品首页| 久久久夜精品| 国际精品欧美精品| 性欧美video另类hd性玩具| 亚洲午夜未删减在线观看| 久久综合亚州| 免费观看一级特黄欧美大片| 国产精品一区二区黑丝| 亚洲视频在线播放| 亚洲自拍偷拍色片视频| 欧美噜噜久久久xxx| 亚洲黄色成人久久久| 1769国内精品视频在线播放| 久久精品视频在线播放| 久久久亚洲人| 在线播放亚洲一区| 久久综合给合久久狠狠色| 美女日韩欧美| 亚洲精品一区二区三| 麻豆精品一区二区av白丝在线| 欧美高清视频| 亚洲精品国产精品乱码不99按摩| 男同欧美伦乱| 亚洲国产小视频| 亚洲一级高清| 国产欧美精品一区| 久久激情五月激情| 欧美不卡视频| 一区二区三区视频在线播放| 欧美三级日本三级少妇99| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 久热re这里精品视频在线6| 在线观看亚洲精品| 欧美激情一区二区三区蜜桃视频 | 欧美韩日一区| 99天天综合性| 国产精品免费一区二区三区在线观看 | 亚洲中字黄色| 国内精品嫩模av私拍在线观看 | 久久精品国产亚洲一区二区三区 | 亚洲一区久久| 国产视频一区在线| 欧美91视频| 亚洲一级黄色av| 免费成人激情视频| aa级大片欧美| 国产在线视频欧美一区二区三区| 久久免费高清| 亚洲私人黄色宅男| 免费久久99精品国产自在现线| 久久亚洲综合色| 久久国产精品72免费观看| 亚洲成人原创| 国产精品青草久久| 久久国产精品黑丝| 在线视频你懂得一区| 麻豆av福利av久久av| 亚洲自拍高清| 亚洲精品三级| 国产自产2019最新不卡| 欧美偷拍一区二区| 免费h精品视频在线播放| 亚洲视频在线观看网站| 欧美福利网址| 久久只精品国产| 午夜精品免费在线| 99国内精品久久| 狠狠色狠狠色综合日日91app| 欧美日韩免费观看中文| 久久伊人精品天天| 欧美在线观看视频在线| 99这里只有精品| 91久久精品一区二区别| 久久亚洲春色中文字幕久久久| 亚洲自拍偷拍视频| 亚洲色诱最新| 在线一区二区视频| 日韩亚洲精品电影| 亚洲丰满在线| 亚洲国产精品久久| 国内精品久久久| 国产精品色在线| 国产精品国产三级国产普通话三级 | 国产精品视频免费在线观看| 欧美精品在线观看播放| 久久久精品免费视频| 欧美一区激情| 久久福利毛片| 欧美综合77777色婷婷| 午夜精品在线| 午夜在线播放视频欧美| 亚洲欧美在线看| 亚洲欧美国产制服动漫| 亚洲欧美电影在线观看| 午夜精品久久久久久99热| 亚洲欧美偷拍卡通变态| 翔田千里一区二区| 久久精品免费电影| 久久午夜av| 欧美成人在线免费观看| 欧美国产一区二区| 欧美日韩亚洲一区二区| 国产精品久久久久久久久久直播| 国产精品激情偷乱一区二区∴| 国产精品啊啊啊| 国产精品日韩一区| 国产日韩欧美精品在线| 极品中文字幕一区| 亚洲黄色高清| 夜夜爽99久久国产综合精品女不卡 | 欧美在线免费视屏| 久久久久久一区二区三区| 欧美a级理论片| 欧美日韩一区二区三区在线视频| 欧美性猛交视频| 国产日韩欧美二区| 亚洲国产影院| 亚洲在线免费视频| 久久久久久成人| 亚洲国产精品一区二区www| av成人福利| 欧美日韩精品一区二区天天拍小说| 欧美日韩精品二区| 国产欧美精品国产国产专区| 激情久久婷婷| 一区二区三区波多野结衣在线观看| 午夜视频一区| 欧美成人中文字幕| 亚洲无线一线二线三线区别av| 久久精品欧美日韩精品| 欧美日韩国产精品成人| 国产亚洲激情在线| 99在线精品观看| 久久久免费av| 99精品欧美一区| 久久精品国产999大香线蕉| 欧美人牲a欧美精品| 国产在线视频欧美| 亚洲在线观看| 亚洲国产成人不卡| 午夜国产不卡在线观看视频| 欧美精品一区二区三区在线看午夜 | 欧美一区二区三区免费观看视频| 另类综合日韩欧美亚洲| 国产精品视频在线观看| 亚洲裸体在线观看| 欧美岛国激情| 欧美在线视频日韩| 国产精品日韩专区| 99re热这里只有精品视频|