蓝桥杯历届试题 国王的烦恼(思维并查集)

题目： C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。
　　如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起*。
　　现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行*。
思路：并查集+思维。
分析：注意到t的范围，我们可以从大到小枚举天数，对天数进行分析。
假设到了第i天，那么前i-1天就不用考虑(因为已经坍塌完了)，如果这天能连接两个新节点，这天过后新节点联系消失，必然会有人*，结果+1。
反思： 并查集就三行代码的事情，可每次总会有卡一下的情况，说明掌握的不是太好。总结一下套路，难一点无非就是逆向思维，把拆边当建立边，很套路的。
ac代码：

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long ll;
const int N=1e4+5;

struct node{
    int f,t;
    node(int f=0,int t=0):f(f),t(t){}
};
vector<node>E[100001];
int fa[N];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    int n,m,f,t,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i;
    while(m--){
        scanf("%d%d%d",&f,&t,&w);
        E[w].push_back(node(f,t));
    }
    int ans=0;
    for(int i=100000;i>=1;i--){
        if(E[i].empty()) continue;
        bool flag=0;
        for(int j=0;j<E[i].size();j++){
            f=E[i][j].f,t=E[i][j].t;
            f=find(f),t=find(t);
            if(f!=t) fa[t]=f,flag=1;
        }
        if(flag) ans++;
    }
    printf("%d\n",ans);
    return 0;
}