如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起*。
现在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。
刚看到这题就想着用暴力。。数据太大，也就没尝试。第一次确实想到并查集，但是我了解的和之前有用过的并查集太单一，没有说类似的题目。也就放弃了。百度！
只要百度一下，后面全部跟着（并查集），我当时也没打开看，我想着自己做试试，是真想不到，因为我一用并查集有好多路径都给覆盖掉了，很多点都会遗漏。 看了好多大佬的博客，才想到。
思路就是根据天数从大到小排序，从大到小开始遍历，如果某个桥的两端不是连通的，他们就会*。因为天数更小的即使使这两端连通，因为天数较小，过了几天后，他们还是不连通。（要注意判断天数相同的情况） 例如例题给的案例 4 4
1 2 2
1 3 2
2 3 1
3 4 3
排序后变成 3,4,3 1,2,2 1,3,2 2,3,1 依次遍历从第一个开始 因为本身3,4并不连通，所以*sum++； 同理1,2也不连通，sum++； 到1,3的时候，1,3也是不连通的，也要*，但是因为提议说是*几天，1,2和1,3的桥都是第二天坏，所以他们是同一天*，sum不变 最后到2,3, 这两点是连通的，所以sum保持不变，
还有点。之前没注意过 我的 find函数是 while(a[x]!=x) x=a[x]; return x; 但是如果这样提交是超时的，只有80分 参考了大佬的代码他们的find函数是 if (a[x]==x) return x;
return a[x]=find(a[x]);
。。差距
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct node{
int x,y,day;
}node;
int a[10000+10]={0};
bool cmp(node n1,node n2){
return n1.day>n2.day;
}
int find(int x){//切记
if (a[x]==x)
return x;
return a[x]=find(a[x]);
}
int add(int x,int y){
x=find(x);
y=find(y);
if(x!=y){
a[x]=y;
return 1;
}
return 0;
}
int main(){
node s[100000+10];
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>s[i].x>>s[i].y>>s[i].day;
}
for(int i=1;i<=n;i++)
a[i]=i;
sort(s,s+m,cmp);
int p=-1,sum=0;//p代表前一天*的时间
for(int i=0;i<m;i++){
int pd=add(s[i].x,s[i].y);
if(pd&&p!=s[i].day){//今天的天数不能和上次*的天数相同，类似于桥1,2和桥1,3
sum++;
p=s[i].day;
}
}
cout<<sum;
return 0;
}
这题挺有收获的，之前认识的并查集太片面....