题目背景

A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

题目描述

给出A地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）

输入输出格式

输入格式：

第1行两个正整数N，M

下面M行，每行3个正整数x, y, t，告诉你这条公路连着x,y两个村庄，在时间t时能修复完成这条公路。

输出格式：

如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1，否则输出最早什么时候任意两个村庄能够通车。

输入输出样例

4 4
1 2 6
1 3 4
1 4 5
4 2 3

5

说明

N<=1000，M<=100000

x<=N，y<=N，t<=100000

很简单的并查集。

解题方法是先按照时间来排序，从先到后。

每修好一个公路，检查一下是否全部完工。

用一个VIS数组来保存已经修好的村庄的数组。

当vis==n而且并查集只有一个集合的时候的时间，就是最小的t

 

#include<iostream>
#include<algorithm>
using namespace std;
int vis[1007];
int father[1007];
int n, m;
struct node {
	int start;
	int end;
	int time;

};
int  cmp(node a, node b) {
	return a.time < b.time;
}
int find(int a) {
	int x = a;
	while(father[x] != x) {
		x = father[x];
	}
	int y = a;
	int z;
	while(father[y] != y) {
		z = y;
		y = father[y];
		father[z] = x;

	}

	return x;

}
int ac() {
	int tot = 0;
	for (int i = 1; i <= n; ++i) {
		if(father[i] == i)
			tot++;
	}
	return tot;
}

void unionx(int a, int b) {
	int fa = find(a);
	int fb = find(b);
	father[fb] = fa;
}

int main() {

	cin >> n >> m;
	node a[100007];
	for (int i = 0; i < 1007; ++i) {
		father[i] = i;
	}
	for (int i = 0; i < m; ++i) {
		cin >> a[i].start >> a[i].end >> a[i].time;
	}
	int complish = 0;

	sort(a, a + m, cmp);
	int flag = -1;
	for (int i = 0; i < m; ++i) {

		unionx(a[i].start, a[i].end);

		if(vis[a[i].start] == 0) {
			complish++;
			vis[a[i].start] = 1;
		}
		if(vis[a[i].end] == 0) {
			complish++;
			vis[a[i].end] = 1;
		}
		if(complish >= n && flag == -1 && ac() == 1) {
			flag = a[i].time;
		}

	}

	cout << flag << endl;



}