问题描述
C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。
如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。
现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。
输入格式
输入的第一行包含两个整数n, m，分别表示小岛的个数和桥的数量。
接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。
输出格式
输出一个整数，表示居民们会抗议的天数。
样例输入
4 4
1 2 2
1 3 2
2 3 1
3 4 3
样例输出
2
样例说明
第一天后2和3之间的桥不能使用，不影响。
第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。
第三天后3和4之间的桥不能使用，居民们会抗议。
数据规模和约定
对于30%的数据，1<=n<=20，1<=m<=100；
对于50%的数据，1<=n<=500，1<=m<=10000；
对于100%的数据，1<=n<=10000，1<=m<=100000，1<=a, b<=n， 1<=t<=100000。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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define MAX 100000+5
struct node{
int a;
int b;
int d;
node(int aa,int bb,int dd):a(aa),b(bb),d(dd){
}
node(){
}
};
node g[MAX];
bool cmp(node a,node b){
return a.d>b.d;}
class unionset{
public:
vector<int> parent;
vector<int> rank;
unionset(int n){
parent=vector<int>(n+1,0);
rank=vector<int>(n+1,0);
for(int i=1;i<=n;i++)
parent[i]=i;
}
bool Union(int u1,int u2){
int p1=find(u1);
int p2=find(u2);
if(p1==p2) return false;
if(rank[p1]>rank[p2]){
parent[p2]=p1;
}
else if(rank[p2]>rank[p1]){
parent[p1]=p2;
}
else {
parent[p1]=p2;
rank[p2]++;
}
return true;
}
int find(int num){
if(num!=parent[num]){
parent[num]=find(parent[num]);//find(num)一直自己调用自己 错的 find(parent[num]) 往上回溯
}
return parent[num];
}
};
int main(){
int n,m;
cin>>n>>m;
int x1,x2,v;
for(int i=0;i<m;i++){
cin>>x1>>x2>>v;
g[i]=node(x1,x2,v);
}
//!! 按边的权值排序 sort(g,g+n,cmp) 错误
sort(g,g+m,cmp);
int pre=-1,cnt=0;
unionset uf(n+1);
for(int i=0;i<m;i++){
if(uf.Union(g[i].a,g[i].b)&&pre!=g[i].d){
cnt++;
pre=g[i].d;
}
}
cout<<cnt<<endl;
}
参考博客