本文共 1704 字，大约阅读时间需要 5 分钟。
并查集定义：
/*并查集模板*/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] 并查集题目：
题意：人之后熟悉的人坐在一起，问需要多少张桌子可以让所有人都坐下。
题意：有很多城镇，它们之间有一些城镇道路互相连通，问最少需要修多少条路，使得所有城镇直接或间接连通。
题意：朋友和朋友站成一堆，不是朋友的站成一堆，问人数最多的一堆的人数。
题意：有很多组学生，在同一个组的学生经常会接触，也会有新的同学的加入。但是SARS是很容易传染的，只要在改组有一位同学感染SARS，那么该组的所有同学都被认为得了SARS。现在的任务是计算出有多少位学生感染SARS了。假定编号为0的同学是得了SARS的。
题意：有N名来自两个帮派的坏蛋，已知一些坏蛋两两不属于同一帮派，求判断给定两个坏蛋是否属于同一帮派。
题意：世界上宗教何其多。假设你对自己学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生，但是你不能直接问学生的信仰，不然他会感到很不舒服的。有另外一个方法是问m对同学，是否信仰同一宗教。根据这些数据，相信聪明的你是能够计算学校最多有多少种宗教信仰的。
题意：用11个图形组成一个n*m的矩形，那么有连通的图形有多少个？
解题思路：将矩形扫一遍，扫的过程中，看它跟它的右边以及下边是否连通，利用并查集将它们连接起来。
题意：在一个无向图里，求a到b的所以路径上权重最大值、最小值之差最小
解题思路：将所有的边按权重排序，枚举最小权重值，然后将权重值从小到大加入路径，知道a和b之间形成通路。
题意：给你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],如果不等于，那么这个答案就是错误的。
题意：有3种动物，互相吃与被吃，现在告诉你m句话，其中有真有假，叫你判断假的个数(如果前面没有与当前话冲突的，即认为其为真话)
题意：有n个完全相同的立方体，我们有两个操作，一：将包含a的一堆放到包含b的一堆的上面，二：求在a的下面有多少个立方体。
题意：有一些货物，每个货物有价值和卖出的截至日期，每天可以卖一个货物，问能卖出的最大价值是多少。
题意：一张图上分布着n台坏了的电脑，并知道它们的坐标。两台修好的电脑如果距离<=d就可以联网，也可以通过其他修好的电脑间接相连。给出操作“O x”表示修好x，给出操作“S x y”，请你判断x和y在此时有没有连接上。
题意：输入n个bug，bug之间有interaction，当前假设异性之间才interaction，但是需要验证，给定这些interaction对，判定是否满足假设。
题意：有一些货物，每个货物有价值和卖出的截至日期，每天可以卖一个货物，问能卖出的最大价值是多少。
转载地址：http://pbbqb.baihongyu.com/