克鲁斯卡尔算法

不开O2 AC

开O2 全部RE

#include<bits/stdc++.h>
using namespace std;
int fa[1000100];
int n,m;
struct Node {
	int x;
	int y;
	int z;
}node[1000100];

inline void start(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
}

int find(int a){
	if(fa[a]==a){
		return fa[a];
	}
	else{
		fa[a]=find(fa[a]);
		return fa[a];
	}
}

int hb(int a,int b){
	fa[find(a)]=find(b);
}

bool cmp(Node a,Node b){
	return a.z<b.z; 
}

int main(){
	int mst=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>node[i].x>>node[i].y>>node[i].z; 
	}
	sort(node+1,node+m+1,cmp);
	start();
	/*
	for(int i=1;i<=m;i++){
		cout<<node[i].x<<" "<<node[i].y<<" "<<node[i].z<<endl;
	}
	*/
	for(int i=1;i<=m;i++){
		int f1=find(node[i].x);
		int f2=find(node[i].y);
		if(f1==f2){
			continue;
		}
		else{
			hb(f1,f2);
			mst+=node[i].z;
		}
	}
	for(int i=1;i<=n;i++){
		if(find(1)!=find(i)){
			cout<<"orz";
			return 0;
		}
		else{
			continue;
		}
	}
	
	cout<<mst<<endl;
	return 0;
}