最小生成树

最小生成是无向图中的一个问题。

kruskal 算法

时间复杂度 ，m 为边的个数

1. 对边进行排序。
2. 用并查集处理连通性问题。

const int maxn = 1e6+1;

struct E{ // 图中的边
    int u, v, w;
}e[maxn];

//struct edge{ // 最小生成树的边
//    int to, w;
//    edge(){}
//    edge(int to, int w): to(to), w(w){}
//}; vector<edge> g[maxn]; // 最小生成树边的存储

int f[maxn]; // 并查集-数组

int fd(int x) { // 并查集-查询
    if (f[x] == x) return x;
    return f[x] = fd(f[x]);
}

void kruskal(int n, int m) { // 最小生成树 - kruskal 算法
    for(int i = 1; i <= n; ++ i) { // 初始化
        f[i] = i;
        g[i].clear();
    }
    sort(e+1, e+m+1, [](E &e1, E &e2){return e1.w<e2.w;});
    for(int i = 1, j = 0; i <= m; ++ i) {
        int a = fd(e[i].u);
        int b = fd(e[i].v);
        if (a == b) continue; // 成环 跳过
        f[b] = a;
//        g[e[i].u].push_back(edge(e[i].v, e[i].w));
//        g[e[i].v].push_back(edge(e[i].u, e[i].w));
        if (++ j == n-1) break; // 树已生成
    }
}