问题描述：
题目背景
AAA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
题目描述
给出A地区的村庄数NNN，和公路数MMM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）
输入格式
第111行两个正整数N,MN,MN,M
下面MMM行，每行333个正整数x,y,tx, y, tx,y,t，告诉你这条公路连着x,yx,yx,y两个村庄，在时间t时能修复完成这条公路。
输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出−1-1−1，否则输出最早什么时候任意两个村庄能够通车。
输入输出样例
输入 #1
4 4
1 2 6
1 3 4
1 4 5
4 2 3
输出 #1
5
说明/提示
N≤1000,M≤100000N \le 1000,M \le 100000N≤1000,M≤100000
x≤N,y≤N,t≤100000x \le N,y \le N,t \le 100000x≤N,y≤N,t≤100000
基本思路：
利用并查集合并集合。
这里除第一行后的每一行都是关于边的信息，每一条边连接哪两个节点，这种题目我们就可以用并查集来做。
唯一的问题就是如何判断我们的集合是否已经包含全部的元素。
这里我的解决方法就是引入一个记录根节点所含元素个数的变量，如果他的个数==n，那么就说明已经完全连同了。
AC代码：
#include<bits/stdc++.h>
using namespace std;
struct Road {
// 两个村庄的编号以及修复路的时间
int x;
int y;
int t;
Road() = default;
Road(int _x, int _y, int _t) :
x(_x), y(_y), t(_t) {}
};
constexpr int kNum = 1005;
int p[kNum]; // 存放父亲节点
int r[kNum]; // 存放集合的秩
int s[kNum]; // 存放集合的元素个数
// 这里竟然也要提供构造函数
vector<Road> road; // 这里的容器好像就是某种特定类型的容器
void Initialize() {
for (int i = 0; i < kNum; ++i) {
p[i] = i;
r[i] = s[i] = 1;
}
}
int Find(int x) {
// 根据元素找相应集合的根节点
// 找到根节点了
if (x == p[x]) {
return x;
}
return p[x] = Find(p[x]);
}
void Union(int x, int y) {
int p_x = Find(x);
int p_y = Find(y);
// 两个元素位于同一个集合中
if (p_x == p_y) {
return;
}
// 两个元素不在同一个集合中
if (r[p_x] > r[p_y]) {
p[p_y] = p_x;
s[p_x] += s[p_y];
} else {
if (r[p_x] == r[p_y]) {
++r[p_y];
}
p[p_x] = p_y;
s[p_y] += s[p_x];
}
}
int main() {
Initialize();
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int q, w, e;
cin >> q >> w >> e;
road.push_back(Road(q, w, e));
}
sort(road.begin(), road.end(), [] (Road x, Road y) { return x.t < y.t; });
for (int i = 0; i < m; ++i) {
Union(road[i].x, road[i].y);
if (s[Find(road[i].x)] == n) {
cout << road[i].t << endl;
return 0;
}
}
cout << "-1\n";
return 0;
}
其他经验：
并查集在使用之前要进行初始化。自定义类的数组，由于不知道可能要放什么元素，所以一般不会进行初始化，这时候就要求你提供默认构造函数了。要明白自己是使用vector还是使用array，后者可能由于不知道会有几个元素，所以预先开辟很多空间——这样就会导致很多没有用的元素会混到我们所需要元素的操作中（比如对数组进行sort排序，那只能begin, end, 但这个显然不对）；vector使用效率可能比array的效率要稍微低一点（开辟新的空间啥的），但是就没有这样的困扰。
