并查集（初级）小结

并查集定义：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 （贪心+并查集） 题意：有一些货物，每个货物有价值和卖出的截至日期，每天可以卖一个货物，问能卖出的最大价值是多少。