并查集（初級）小結

并查集定義：https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86

/*并查集模闆*/
int parent[MAXN];
int rank[MAXN];

void init(int n){
    for (int i=0;i<=n;i++){
        parent[i]=i;
        rank[i]=0;
    }
}
int find(int x){
    if (x==parent[x])
        return x;
    int temp=parent[x];
    parent[x]=find(parent[x]);
    rank[x]+=rank[temp];
    return parent[x];
}
void union(int x,int y){
    x=find(x),y=find(y);
    if (x==y)    return ;
    if (rank[x]<rank[y])
        parent[x]=y;        
    else{
        parent[y]=x;
        if (rank[x]==rank[y])
            rank[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}
           

并查集題目：

簡單題： hdu1213 How Many Tables (統計樹的個數) 題意：人之後熟悉的人坐在一起，問需要多少張桌子可以讓所有人都坐下。 hdu1232 暢通工程  （統計樹的個數） 題意：有很多城鎮，它們之間有一些城鎮道路互相連通，問最少需要修多少條路，使得所有城鎮直接或間接連通。 hdu1856 More is better (統計樹的大小) 題意：朋友和朋友站成一堆，不是朋友的站成一堆，問人數最多的一堆的人數。 poj1308 Is It A Tree? 題意：判斷這個圖是不是樹。 poj1611 The Suspects 題意：有很多組學生，在同一個組的學生經常會接觸，也會有新的同學的加入。但是SARS是很容易傳染的，隻要在改組有一位同學感染SARS，那麼該組的所有同學都被認為得了SARS。現在的任務是計算出有多少位學生感染SARS了。假定編号為0的同學是得了SARS的。 poj1703 Find them, Catch them 題意：有N名來自兩個幫派的壞蛋，已知一些壞蛋兩兩不屬于同一幫派，求判斷給定兩個壞蛋是否屬于同一幫派。 poj2524 Ubiquitous Religions 題意：世界上宗教何其多。假設你對自己學校的學生總共有多少種宗教信仰很感興趣。學校有n個學生，但是你不能直接問學生的信仰，不然他會感到很不舒服的。有另外一個方法是問m對同學，是否信仰同一宗教。根據這些資料，相信聰明的你是能夠計算學校最多有多少種宗教信仰的。

中等題： hdu1198 Farm Irrigatio (統計樹的個數) 題意：用11個圖形組成一個n*m的矩形，那麼有連通的圖形有多少個？ 解題思路：将矩形掃一遍，掃的過程中，看它跟它的右邊以及下邊是否連通，利用并查集将它們連接配接起來。 hdu1598 find the most comfortable road (貪心+并查集) 題意：在一個無向圖裡，求a到b的是以路徑上權重最大值、最小值之差最小 解題思路：将所有的邊按權重排序，枚舉最小權重值，然後将權重值從小到大加入路徑，知道a和b之間形成通路。 hdu3038 How Many Answers Are Wrong (并查集的應用) 題意：給你m個a,b,v表示a到b之間的和為v，問你有幾個錯誤的。 解題思路：先進行優化，我們将[a,b]改成(a-1,b]，這樣當我們知道[a,b],[b+1,c]時就可以直接求出[a,c]的值。對于(a,b]我們使得a的父節點為b，那麼我們在判别(c,b]的和為v是否成立時，我們隻需要判斷(a,c]+(c,b]是否等于(a,b],如果不等于，那麼這個答案就是錯誤的。 poj1182 食物鍊 （關系并查集） 題意：有3種動物，互相吃與被吃，現在告訴你m句話，其中有真有假，叫你判斷假的個數(如果前面沒有與目前話沖突的，即認為其為真話) poj1988 Cube Stacking （關系并查集） 題意：有n個完全相同的立方體，我們有兩個操作，一：将包含a的一堆放到包含b的一堆的上面，二：求在a的下面有多少個立方體。

poj1456 Supermarket （貪心+并查集） 題意：有一些貨物，每個貨物有價值和賣出的截至日期，每天可以賣一個貨物，問能賣出的最大價值是多少。 poj2236 Wireless Network  題意：一張圖上分布着n台壞了的電腦，并知道它們的坐标。兩台修好的電腦如果距離<=d就可以聯網，也可以通過其他修好的電腦間接相連。給出操作“O x”表示修好x，給出操作“S x y”，請你判斷x和y在此時有沒有連接配接上。 poj2492 A Bug's Life （關系并查集） 題意：輸入n個bug，bug之間有interaction，目前假設異性之間才interaction，但是需要驗證，給定這些interaction對，判定是否滿足假設。

poj1456 Supermarket （貪心+并查集） 題意：有一些貨物，每個貨物有價值和賣出的截至日期，每天可以賣一個貨物，問能賣出的最大價值是多少。