链接: https://www.luogu.org/problemnew/show/P1111
思路: 简单的并查集, 一开始想的是每合并一次就遍历一遍看看是否全部连通了, 看了题解才知道只要用一个变量标志连通块数量即可, 每次合并连通块数量减一
代码:
- //#include<bits/stdc++.h>
- #include<iostream>
- #include<vector>
- #include<stack>
- #include<string>
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- #include<map>
- #include<set>
- #include<cmath>
- #define inf 0x3f3f3f3f
- using namespace std;
- typedef long long ll;
- const int M = int(1e5) * 2 + 5;
- //vector<int> v;
- struct node
- {
- int x, y, t;
- }a[M];
- bool cmp(node a, node b)
- {
- return a.t <b.t;
- }
- int root[M];
- void init()
- {
- for (int i = 0; i < M; i++) root[i] = i;
- }
- int Find(int x)
- {
- int r = x;
- while (root[r] != r)
- {
- r = root[r];
- }
- int i;
- while (root[x] != r)
- {
- i = root[x];
- root[x] = r;
- x = i;
- }
- return r;
- }
- void merge(int x, int y)
- {
- x = Find(x);
- y = Find(y);
- if (x != y) root[x] = y;
- }
- signed main()
- {
- int n, m;
- cin>> n>> m;
- for (int i = 0; i <m; i++)
- {
- cin>> a[i].x>> a[i].y>> a[i].t;
- }
- sort(a, a + m, cmp);
- init();
- int cnt = n;
- for (int i = 0; i < m; i++)
- {
- int x = Find(a[i].x);
- int y = Find(a[i].y);
- if (x != y)
- {
- cnt--;
- merge(x, y);
- }
- if (cnt == 1)
- {
- cout << a[i].t;
- return 0;
- }
- }
- cout << -1;
- return 0;
- }
备注: 每次合并前要检查两个村庄是否属于同一个连通块
来源: http://www.bubuko.com/infodetail-3013243.html