Kruskal算法-2025/11/24

Kruskal算法

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5  + 10;

struct Edge{
	int a,b,c;
	bool operator<(const Edge &edge) const{
		return c < edge.c;
	}
};

Edge edge[N];
int n , m;
int p[N];

int find(int x){
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}

int main(){
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++) p[i] = i;
	
	for(int i = 1; i <= m; i++){
		int a,b,c;
		cin >> edge[i].a >> edge[i].b >> edge[i].c;
	}
	
	sort(edge + 1, edge + 1 + m);
	
	int res = 0, cnt = 0;
	for(int i = 1; i <= m; i++){
		int a = edge[i].a , b= edge[i].b, c = edge[i].c;
		a = find(a) , b = find(b);
		if(a != b) {
			res += c;
			p[a] = b;
			cnt ++;
		}
	}
	
	if(cnt < n - 1) puts("impossible");
	else cout << res << "\n";
	
	return 0;
}