简介
并查集是什么
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
并查集其实就是一个树，如果要合并的话就将其中一个的根节点连接到另外一个的根节点上。在询问他们是否在一个集合中是，只需要看一下他们的跟是不是同一个就可以了。
并查集可以干什么
并查集可以比一般数组与链表相比较为高效的将两个集合合并，并且还可以判断连个节点是否在一个集合中
主要操作
初始化
把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(n)。
查找
查找元素所在的集合，即根节点。
合并
将两个元素所在的集合合并为一个集合。
通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的“查找”操作实现。
代码实现
普通并查集的代码实现
定义
为了便于并查集查询，并查集的存储方式是祖先存出法。
int father[N];
找根
不断地找父节点的父节点，直到这个节点没有了父节点
int find_root(int x)
{
if (x == father[x])
return x;
return find_root(father[x]);
}
判断是否在一个集合
如果他们的根节点是一个，那么他们就在一个集合中，否则就在不同集合
bool together(int x,int y)
{
if(find_root(x)==find_root(y))
return 1;
return 0;
}
合并
将其中一个根节点连接到另外一个根节点
void merge(int x, int y)
{
int rx = find_root(x), ry = find_root(y);
if (!(together(x,y)))
father[rx] = ry;
return;
}
并查集的优化
在合并的时候我们应该将较小的并查集合并到较大的并查集上，因为这样不会增加并查集的度。
只有在两个并查集的度相同时，在合并时度才会增加。
因为在连接时，并不能将每一个节点全部连接到另外一个根节点上，所以在找根是，如果发现没有链接，就直接链接到根节点。
定义
在定义时，不光要储存父节点，还要为了在合并时总能将度小的并查集合并大度高的并查集中，所以要定义height来存储每棵树的大小。
int father[N], height[N]
找根
如果在找根的时候发现不是直接连接着根节点，就用ret来记录一下，顺便合并到根节点。
int find_root(int x)
{
if (x == father[x])
return x;
int ret = find_root(father[x]);
father[x] = ret;
return ret;
}
合并
为了尽可能的降低并查集的度，让并查集在找根时快一点。在合并时会将度较小的合并到度较大的并查集中。
void merge(int x, int y)
{
int rx = find_root(x);
int ry = find_root(y);
if (rx == ry)
return;
if (height[rx] == height[ry])
height[ry]++;
if (height[rx] > height[ry]) {
int a = rx;
rx = ry;
ry = a;
}
father[rx] = ry;
}
例题
「NOIP2010」关押罪犯
题目描述
S 城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 $N,M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 $M$ 行每行为三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。数据保证 $1<a_j\leq b_j\leq N, 0 < c_j\leq 10^9$，且每对罪犯组合只出现一次。
输出格式
共 $1$ 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出0。
输入样例
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出样例
3512
说明
罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是\(3512\)（由\(2\)号和\(3\)号罪犯引发）,其他任何分法都不会比这个分法更优。
对于\(30pts\)的数据有\(N≤15\)。
对于\(60pts\)的数据有\(N≤2000,M≤50000\)。
对于\(100pts\)的数据有\(N≤20000,M≤100000\)。
AC code
#include<bits/stdc++.h>
const int N=200000;
int father[N],height[N],n,m;
struct A{
int f,s,w;
}data[N];
inline bool cmp(A a,A b){
if(a.w<b.w)
return 0;
return 1;
}int find_root(int x){
if(x==father[x])
return x;
int ret=find_root(father[x]);
father[x]=ret;
return ret;
}inline void merge(int x,int y){
int rx=find_root(x);
int ry=find_root(y);
if(rx==ry)
return ;
if(height[rx]==height[ry])
height[ry]++;
if(height[rx]>height[ry]){
int a=rx;
rx=ry;
ry=a;
}father[rx]=ry;
}int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n*2;++i)
father[i]=i;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&data[i].f,&data[i].s,&data[i].w);
std::sort(data+1,data+m+1,cmp);
for(int i=1;i<=m;++i){
int t1=find_root(data[i].f),t2=find_root(data[i].s);
if(t1==t2){
printf("%d\n",data[i].w);
return 0;
}merge(data[i].f,data[i].s+n);
merge(data[i].s,data[i].f+n);
}printf("0\n");
return 0;
}