题目
S城现有两座*，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c的冲突事件。每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。在详细考察了N名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使Z市长看到的那个冲突事件的影响力最小？这个最小值是多少？
分析
这是高中时候做的一道并查集（因为当时不太明白所以印象格外深刻），今天在补比赛题的时候遇到了一道并查集突然想起来这道，拿出来写一下。
我觉得并查集有两种最常见的应用啊，一种是一个集合，一种是两个集合。
比如说给你一些边让你判断环，对于每一条边要把他们加入这一个集合，当某一条边还没加就已经在一个集合的时候说明有环。这种应用是最常见的。
还有一种是两个集合。比如说这道题。
先把所有的仇恨关系从大到小排序。由大到小的处理每一个仇恨关系，p[x]=find(y+n)代表x和y在两个集合中（不同集合或者叫补集？）。当处理某一条关系的时候，如果x==y，则说明这两个犯人在同一个集合，则这个仇恨关系的值就是要找的答案。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream> using namespace std;
const int maxn=+;
const int maxm=+;
int n,m;
struct Edge {
int a,b,c;
bool operator <(const Edge&rhs)const{
return c>rhs.c;
}
}edge[maxm];
int p[*maxn];
int find(int x){
return p[x]==x?x:p[x]=find(p[x]);
}
int ans;
int main(){
scanf("%d%d",&n,&m);
ans=;
for(int i=;i<=m;i++){
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].c);
}
sort(edge+,edge++m);
for(int i=;i<=*n;i++)p[i]=i; for(int i=;i<=m;i++){
int x=find(edge[i].a),y=find(edge[i].b);
if(x==y){
ans=edge[i].c;
break;
}
p[x]=find(edge[i].b+n);
p[y]=find(edge[i].a+n);
}
cout<<ans<<endl;
return ;
}