最小生成树模板及其dfs总结 （kruskal prim）

克鲁斯卡尔
利用并查集，将排好序的每条边，如果不存在于并查集中就依次插入
上模板，方便查阅

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
#define inf 0x3f3f3f3f
int fa[N];
int n, m;
struct edge
{
    int u, v, w;bool operator < (edge b) {
     return w < b.w; }
}edges[N];int find(int x)
{
    if (x == fa[x])return x;return fa[x] = find(fa[x]);
}
int kruskal()
{
    int ans = 0, sum = 0;sort(edges + 1, edges + 1 + m);for (int i = 1; i <= m; i++){
    int u = edges[i].u, v = edges[i].v, w = edges[i].w;int fx = find(u), fy = find(v);if (fx != fy){
    fa[fx] = fy;ans += w;sum++;}if (sum == n - 1)return ans;}return -1;
}
int main()
{
    cin >> n >> m;for (int i = 1; i <= n; i++)//并查集初始化fa[i] = i;for (int i = 1; i <= m; i++){
    int u, v, w;scanf_s("%d%d%d", &u, &v, &w);edges[i] = {
     u,v,w };}int ans = kruskal();if (ans == -1)cout << "impossible" << endl;elsecout << ans <<