蓝桥杯历届试题-国王的烦恼 （C++代码）

解题思路:


并查集。逆向思维。


注意事项:

看清题目，求抗议的天数，不是最开始的抗议时间。



参考代码:

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct cun{
    	int x;
    	int y;
    	int t;
	}p[100010];
bool cmp(cun a,cun b){
    	return a.t>b.t;
	}
int n,m,q,f[10005];
int find(int a){
	if(f[a]==a)return a;
	return f[a]=find(f[a]);
}
int main()
{	cin>>n;
    cin>>m;   
    for(int i=1;i<=n;i++){
    	f[i]=i;
	}	
	for(int i=1;i<=m;i++){
		cin>>p[i].x>>p[i].y>>p[i].t;
	}
	sort(p+1,p+m+1,cmp);
	int q=-1,sum=0;
	for(int i=1;i<=m;i++){
		if(find(p[i].x)!=find(p[i].y)){
			f[find(p[i].x)]=find(p[i].y);
			if(p[i].t!=q){
        	sum++;
        	q=p[i].t;
		}
		}
        
		}	
	cout<<sum;	
    return 0;
}