题目背景
AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出A地区的村庄数NN，和公路数MM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入格式
第11行两个正整数N,MN,M
下面MM行，每行33个正整数x, y, tx,y,t，告诉你这条公路连着x,yx,y两个村庄，在时间t时能修复完成这条公路。
输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出-1−1，否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入 #1复制
4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出 #1复制
5
说明/提示
N \le 1000,M \le 100000N≤1000,M≤100000
x \le N,y \le N,t \le 100000x≤N,y≤N,t≤100000
代码：
1 #include <algorithm>
2 #include <cstdio>
3 using namespace std;
4
5 struct Road
6 {
7 int x,y,t;
8 // x，y为道路连接的两个村庄
9 //t为修建道路所需要的时间，利用t给道路进行排序
10 };
11
12 int villages[1003]; //村庄 villages[x] = y 代表x的根节点为y，初始值为0
13 Road roads[100003]; //道路个数
14
15 bool cmp(const Road &a,const Road &b)
16 {
17 return a.t < b.t;
18 } //自定义一个cmp函数作为sort()的第三参数，以t为参照升序排序
19
20 int find(int x) //寻找x的上一节根节点,并执行路径压缩算法
21 {
22 int res = x; //储存x
23 while (villages[res])
24 {
25 res = villages[res]; //查：如果res不是根节点，就往上继续
26 }
27 //此时，res已经是根节点了
28 while (x!=res)
29 {
30 int tmp = villages[x];
31 villages[x] = res;
32 x = tmp;
33 } //路径压缩算法 将所有节点都放在第二层，一层一层上升
34 return res;
35 }
36
37 bool unions(int u,int v)
38 {
39 int fu = find(u),fv = find(v); //找到两个节点的根并比较
40 if (fu != fv)
41 {
42 villages[fu] = fv;
43 return true;
44 }
45 return false; //防止重复赋值
46 }
47
48 int main()
49 {
50 int n,m;
51 scanf("%d%d",&n,&m); //村庄数n，公路数m
52 for (int i = 0;i < m;++i)
53 {
54 scanf("%d%d%d",&roads[i].x,&roads[i].y,&roads[i].t);
55 }
56 sort(roads,roads + m,cmp);
57 for (int i = 0;i < m; ++i)
58 {
59 n -= unions(roads[i].x,roads[i].y);
60 if (n == 1)
61 {
62 printf("%d\n",roads[i].t);
63 break;
64 }
65 }
66 if (n > 1)
67 {
68 printf("-1\n");
69 }
70 return 0;
71 }
