蓝桥 历届试题 国王的烦恼

求连通分支的数目

逆向思维：首先按时间对桥梁排序，然后从最后的一座桥开始枚举，要是跟上一一座桥不在同一时间，而且他让两座岛屿产生的新的联系ans加一

（等价于正向的时候把时间相同的桥删除，判断是否让某些岛屿孤立）。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a,b,ans=0,lastday=-1;
int pre[10010];
struct node {
	int x,y,day;
} e[100010];
bool cmp (node a,node b) {
	return a.day>b.day;
}
int find(int x) {
	/*int r=x;
	while (pre[r]!=r) r=pre[r];
	return r;*/
	return pre[x]==x?x:pre[x]=find(pre[x]);    //不这样写会超时 
}
bool vis(int x,int y) {
	a=find(x);
	b=find(y);
	if (a==b) return false;
    pre[b]=a;
	return true;
}
int main()
{
	scanf ("%d%d",&n,&m);
	for (int i=0;i<m;i++) 
		scanf ("%d%d%d",&e[i].x,&e[i].y,&e[i].day);
    sort(e,e+m,cmp);
    for (int i=1;i<=n;i++) pre[i]=i;
	for (int i=0;i<m;i++) {
		if (vis(e[i].x,e[i].y) && e[i].day!=lastday) {  ////两个小岛不连通，且与上一个大桥的天数不同
			ans++;
			lastday=e[i].day;
		}
	}
	printf ("%d\n",ans);
	return 0;
}