链接：https://www.luogu.org/problemnew/show/P1111
思路：简单的并查集，一开始想的是每合并一次就遍历一遍看看是否全部连通了，看了题解才知道只要用一个变量标志连通块数量即可，每次合并连通块数量减一
代码：
1 //#include<bits/stdc++.h> 2 #include<iostream> 3 #include<vector> 4 #include<stack> 5 #include<string> 6 #include<cstdio> 7 #include<algorithm> 8 #include<queue> 9 #include<map> 10 #include<set> 11 #include<cmath> 12 #define inf 0x3f3f3f3f 13 using namespace std; 14 typedef long long ll; 15 const int M = int(1e5) * 2 + 5; 16 //vector<int> v; 17 struct node 18 { 19 int x, y, t; 20 }a[M]; 21 bool cmp(node a, node b) 22 { 23 return a.t < b.t; 24 } 25 26 int root[M]; 27 void init() 28 { 29 for (int i = 0; i < M; i++) root[i] = i; 30 } 31 int Find(int x) 32 { 33 int r = x; 34 while (root[r] != r) 35 { 36 r = root[r]; 37 } 38 int i; 39 while (root[x] != r) 40 { 41 i = root[x]; 42 root[x] = r; 43 x = i; 44 } 45 return r; 46 } 47 void merge(int x, int y) 48 { 49 x = Find(x); 50 y = Find(y); 51 if (x != y) root[x] = y; 52 } 53 signed main() 54 { 55 int n, m; 56 cin >> n >> m; 57 for (int i = 0; i < m; i++) 58 { 59 cin >> a[i].x >> a[i].y >> a[i].t; 60 } 61 sort(a, a + m, cmp); 62 init(); 63 int cnt = n; 64 for (int i = 0; i < m; i++) 65 { 66 int x = Find(a[i].x); 67 int y = Find(a[i].y); 68 if (x != y) 69 { 70 cnt--; 71 merge(x, y); 72 } 73 if (cnt == 1) 74 { 75 cout << a[i].t; 76 return 0; 77 } 78 } 79 cout << -1; 80 return 0; 81 }
备注：每次合并前要检查两个村庄是否属于同一个连通块