并查集 反向记录时间

问题 1435: [蓝桥杯][历届试题]国王的烦恼

时间限制: 1Sec 内存限制: 128MB 提交: 810 解决: 217

题目描述
C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。

如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。

现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。

下文中的样例说明
第一天后2和3之间的桥不能使用，不影响。
第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。
第三天后3和4之间的桥不能使用，居民们会抗议。
数据规模和约定
对于100%的数据，1< =n< =10000，1< =m< =100000，1< =a, b< =n， 1< =t< =100000。

输入
输入的第一行包含两个整数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

思路：
这道题要反着来，如果两个岛之间建完边可以连通，那居民肯定会抗议。

#include<bits/stdc++.h>
using namespace std;
const	int N=20010;
int p[N]; struct node{
   
	int b1;
	int b2;
	int d;

}nn[100005]; bool cmp(const node a,const node b)
	{
   
		return a.d>b.d;
	 } 
int find(int a)
{
   
	if(p[a]!=a)
	p[a]=find(p[a]);
	return p[a];
}
int main()
{
   
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	p[i]=i;
	for(int i=0;i<m;i++)
	{
   
		int a,b,c;
		cin>>a>>b>>c; nn[i]={
   a,b,c};
	 } 
	 sort(nn,nn+m,cmp);
	 int cnt=0;
	 int  tt=-1;
	 for(int i=0;i<m;i++)
	 {
   
	 	if(find(nn[i].b1)!=find(nn[i].b2))
	 	{
   
	 		p[find(nn[i].b1)]=p[find(nn[i].b2)]; if(tt!=nn[i].d)
	 		{
   
			 cnt++;
	 		tt=nn[i].d;}
		 }
	 }
	 printf("%d\n",cnt);
	 return 0;
}