Kruskal算法求最小生成树

rt

所有的边权录入，然后根据权排序，从小到大构成最小生成树。使用并查集，确保在一个联通的不要再更新。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;struct abv{int a;int b;int v;
};bool compareb(abv& x, abv& y){return x.v < y.v;
}int find(int a, vector<int>& P){if(a == P[a])return a;else{P[a] = find(P[a],P);return P[a];}
}void merge(int a, int b, vector<int>& P){int fa = find(a,P);int fb = find(b,P);P[fa] = fb;
}int main()
{int n,m;int a,b,v;cin >> n >> m;vector<abv> ev; abv X;while (m -- ){cin >> a >> b>> v;X.a = a;X.b = b;X.v = v;if(a!=b)ev.push_back(X);}sort(ev.begin(),ev.end(),compareb);vector<bool> inflag(n+1,false);vector<int> P(n+1);for (int i = 1; i <= n; i ++ ) P[i] = i;int count = 0;int total = 0;int p = 0;while(p<ev.size()&&count!=n-1){int u = ev[p].a;int t = ev[p].b;int w = ev[p].v;if(find(u,P)==find(t,P)){p++;continue;}merge(u,t,P);count ++;p++;total += w;}if(count == n-1)cout << total;else cout << "impossible"<<endl;return 0;
}