问题描述
C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。
如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。
现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。
输入格式
输入的第一行包含两个整数n, m，分别表示小岛的个数和桥的数量。
接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。
输出格式
输出一个整数，表示居民们会抗议的天数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17样例输入
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 | #include<iostream> |
错误代码
忽略排完序后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
80
81#include<iostream>
#include<vector>
#include<cstring>
#include<sstream>
#define MAX 1000005
#include<algorithm>
#define INF 0x3f3f3f
using namespace std;
vector<int> vec;
struct bridge{
int a,b,t;
bridge(int aa,int bb,int tt):a(aa),b(bb),t(tt){
}
bridge(){
}
};
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];
}
};
bool cmp(bridge b1,bridge b2){
return b1.t>b2.t;
}
int main(){
int n,m;
cin>>n>>m;
unionset u(n);
bridge br[m];
for(int i=0;i<m;i++){
int a,b,c;
cin>>br[i].a>>br[i].b>>br[i].t;
}
int sum=0;
sort(br,br+m,cmp);
//天数可能是相等
for(int i=0;i<m;i++){
int f1=u.find(br[i].a);
int f2=u.find(br[i].b);
cout<<f1<<" "<<f2<<endl;;
if(f1!=f2) {
sum++;
u.Union(f1,f2);
}
}
cout<<sum<<endl;
}
参考链接
https://blog.csdn.net/u014665013/article/details/45498425