問題描述 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。
剛看到這題就想着用暴力。。資料太大，也就沒嘗試。第一次确實想到并查集，但是我了解的和之前有用過的并查集太單一，沒有說類似的題目。也就放棄了。百度！
隻要百度一下，後面全部跟着（并查集），我當時也沒打開看，我想着自己做試試，是真想不到，因為我一用并查集有好多路徑都給覆寫掉了，很多點都會遺漏。 看了好多大佬的部落格，才想到。
思路就是根據天數從大到小排序，從大到小開始周遊，如果某個橋的兩端不是連通的，他們就會抗議。因為天數更小的即使使這兩端連通，因為天數較小，過了幾天後，他們還是不連通。（要注意判斷天數相同的情況） 例如例題給的案例 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;
}
這題挺有收獲的，之前認識的并查集太片面....
歡迎大家加入 早起學習群，一起學習一起進步！（群号： 642179511 ）