题目背景
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 }