1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1000010
#define maxm 2000010
using namespace std;
int n, m;
int fa[maxn], dep[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, dep[i] = 1; }
int find(int x) { while (x != fa[x]) x = fa[x]; return x; }
int st[maxn], top;
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return ;
if (dep[fx] > dep[fy]) swap(fx, fy);
fa[fx] = fy; st[++top] = fx;
if (dep[fx] == dep[fy]) ++dep[fy], st[top] *= -1;
}
void undo(int _top) {
while (top > _top) {
int x = st[top--];
if (x < 0) x = -x, --dep[fa[x]];
fa[x] = x;
}
}
struct Edge {
int fr, to;
}; vector<Edge> a[maxn];
void solve(int l, int r) {
if (l == r) {
if (top == n - 1) cout << l << "\n", exit(0);
return ;
} int m = l + r >> 1, _top = top;
for (int i = m + 1; i <= r; ++i)
for (auto u : a[i]) merge(u.fr, u.to);
solve(l, m); undo(_top);
for (int i = l; i <= m; ++i)
for (auto u : a[i]) merge(u.fr, u.to);
solve(m + 1, r); undo(_top);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m; init_fa(n);
for (int i = 1; i <= m; ++i) {
int x, y, z; cin >> x >> y >> z;
a[z].push_back({ x, y });
} solve(0, 100001);
return 0;
}
|