并查集!!!! #2 等WA 求大佬指点
查看原帖
并查集!!!! #2 等WA 求大佬指点
202606
轻绘楼主2020/11/4 16:22
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int n,m;
int fa[300000];
int find(int x){
	if(fa[x]!=x)
		return fa[x]=find(fa[x]);
	return x;
}
struct node{
	int x,y,v;
}a[300000];
bool cmp(node x,node y){
	return x.v>y.v;
}
int ioi[3000000];
int main(){
	//freopen("2.in","r",stdin);
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		a[i].x=read();
		a[i].y=read();
		a[i].v=read();
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		int p;
		if(fa[a[i].x]==fa[a[i].y]){
			printf("%d",a[i].v);
			return 0;
		}
		if(!ioi[a[i].x]){
			ioi[a[i].x]=a[i].y;
		}
		else{
			fa[find(a[i].x)]=find(ioi[a[i].y]);
		}
		if(!ioi[a[i].y]){
			ioi[a[i].y]=a[i].x;
		}
		else{
			fa[find(a[i].y)]=find(ioi[a[i].x]);
		}
		p=find(a[i].x);
		p=find(a[i].y); 
	}
	printf("0");
	return 0;
}
2020/11/4 16:22
加载中...