关押罪犯（分多个集合！！）

链接：https://ac.nowcoder.com/acm/problem/16591
来源：牛客网

S 城现有两座*，一共关押着N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为c 的冲突事件。

每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入描述:
第一行为两个正整数N和M，分别表示罪犯的数目以及存在仇恨的罪犯对数。
接下来的M行每行为三个正整数aj，bj，cj，表示aj号和bj号罪犯之间存在仇恨，其怨气值为cj。
数据保证1≤aj＜bj≤N，0＜cj≤1,000,000,000，且每对罪犯组合只出现一次。
输出描述:
共1行，为Z市长看到的那个冲突事件的影响力。如果本年内*中未发生任何冲突事件，请输出0。
示例1
输入
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
输出
3512

思路很明显，将每一对罪犯按照怒气值从大到小排序。再按怒气值从大到小判断每一对罪犯，如果他们不在同一个*(集合)或未被分配*，那么直接把他们分配到两个不同的*，可以避免怒气值较大的一对被分到同一个*。如果两个罪犯已经被分配到同一个*，那么他们只能在同一个*，那么他们之间的怒气值就无法避免，由于我们按怒气值从大到小判断，所以这个怒气值就是无法避免的最大的怒气值，直接输出就好了。

分集合：当我们遍历到某一对罪犯的时候，我们不知道要将他们放在第一个*还是第二个*，所以我们将遍历到的两个罪犯视为放到对立的两个*，例如罪犯1、2、3,共有10个罪犯。
如果遍历到了1与2
那么此时将1的父节点修改为2+10的父节点，2的父节点修改为1+10的父节点。
接下来遍历到2与3同理父节点分别变为3+10的父节点和2+10的父节点。
遍历到这里此时1，3进一个*，2进一个*。如果候面再遍历到1与3，
可以看出1与3的父节点都是2+10的父节点(就是他们有同一个罪犯不在他们所在的*)那么1和3就要进入同一*。

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn = 1e5 + 9;
int fa[maxn], n, m;

struct people {
	int p1, p2, power;
}per[maxn];

bool cmp(people b1, people b2) {
	return b1.power > b2.power;
}

void init() {
	for (int i = 0; i < maxn; i++)fa[i] = i;
}

int qfind(int x) {
	if (fa[x] == x)return x;
	return fa[x] = qfind(fa[x]);
}

void join(int x, int y) {
	int xx = qfind(x), yy = qfind(y);
	if (xx != yy)fa[xx] = yy;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> per[i].p1 >> per[i].p2 >> per[i].power;
	}
	init();
	sort(per + 1, per + 1 + m, cmp);
	for (int i = 1; i <= m; i++) {
		if (qfind(per[i].p1) == qfind(per[i].p2)) {
			cout << per[i].power;
			return 0;
		}
		fa[qfind(per[i].p1)] = qfind(per[i].p2 + n);
		fa[qfind(per[i].p2)] = qfind(per[i].p1 + n);
	}
	cout << 0;
}