题解 | 【模板】最小生成树 Kruskal + 并查集

最小生成树一般有两种方法，即Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法。前者以边来生成，后者以顶点来生成。这里介绍Kruskal算法。

具体思路是，将所有m条边按照权重w从小到大排序，然后遍历其中的每一条边，判断该边的两个顶点是否联通，若没有联通，则选取该边，并将两个顶点联通。

这里一个比较关键步骤就是判断两个点是否联通，可以使用并查集。若两个点联通，则这两个点在同一个集合中，否则不在一个集合中。

下面是代码。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class UnionFindSet {
  public:
    UnionFindSet(int n) : ufs(n + 1, -1) {
    }

    int findRoot(int x) {
        while (ufs[x] > 0) {
            x = ufs[x];
        }
        return x;
    }

    void merge(int x1, int x2) {
        int root1 = findRoot(x1);
        int root2 = findRoot(x2);
        if (root1 == root2) return;
        if (root1 > root2) swap(root1, root2);
        ufs[root1] += ufs[root2];
        ufs[root2] = root1;
    }

    bool inSet(int x1, int x2) {
        return findRoot(x1) == findRoot(x2);
    }

  private:
    vector<int> ufs;
};

struct edge {
    int id, u, v, w;
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFindSet ufs(n);
    vector<edge> ed(m);
    vector<int> edAns;
    edAns.reserve(n - 1);
    for (int i = 0; i < m; ++i) {
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
        ed[i].id = i + 1;
    }
    sort(ed.begin(), ed.end(), [](edge e1, edge e2) {
        return e1.w < e2.w;
    });
    long long sum = 0;
    for (int i = 0; i < m; ++i) {
        if (ufs.inSet(ed[i].u, ed[i].v)) continue;
        ufs.merge(ed[i].u, ed[i].v);
        edAns.push_back(ed[i].id);
        sum += ed[i].w;
    }
    cout << sum << endl;
    for (int& i : edAns) {
        cout  << i << " ";
    }
}