国王的烦恼(蓝桥杯-并查集)

问题描述 　　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之间的桥不能使用，居民们会抗议。

解题思路：采用并查集的思想，逆向的将树建一遍，所以这里我需要对天数排序，从大到小进行排序。接着进行建树，在建树的过程中不断地进行判断，我之前是否有这个桥，如果没有那么就抗议次数++。这里还有一个需要注意的就是：前一次是在第几天抗议的，如果是同一天的话就不要++了，所以这里要特殊判断一下。

上述都是看别人题解粘过来的。其实这题很有趣在于，它是逆向建树，大家想想要是某时间断桥逆向来想不就是在某时间建桥呗，只要算的是多少组同时建起来那就是答案了。

#include<stdio.h> #include<algorithm> using namespace std; int pre[10020]; typedef struct point{ int r,l,t; }p; int cmp(p x,p y){ return x.t>y.t; } int find(int x) { return pre[x]==x?x:pre[x]=find(pre[x]); } int main() { int maxt=100020,mint=-1; int n,m,ans=0; p a[100020]; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d%d",&a[i].r,&a[i].l,&a[i].t); } sort(a,a+m,cmp); for(int i=1;i<=n;i++){ pre[i]=i; } int pre_time=-1; for(int i=0;i<m;i++){ int fu=find(a[i].l); int fv=find(a[i].r); if(fu!=fv){ pre[fu]=fv; if(pre_time!=a[i].t) ans++; pre_time=a[i].t; } } printf("%d\n",ans); return 0; }