并查集判断连通块数-克鲁斯卡尔 | #畅通工程#

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

class UnionFind {
  private:
    vector<int> f;
    vector<int> rank;
  public:
    UnionFind(int n): f(n+1,0), rank(n+1,0) {
        for (int i = 1; i <= n; i++) {
            f[i] = i;
        }
    }

    void merge(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            if (rank[rx] > rank[ry]) {
                f[ry] = rx;
            } else if (rank[rx] < rank[ry]) {
                f[rx] = ry;
            } else {
                f[ry] = rx;
                rank[rx]++;
            }
        }
    }

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

    //统计并查集0节点下的节点个数
    int count() {
        int cnt = 0;
        int rt = find(0);
        for (int i = 0; i < f.size(); i++) {
            if (rt == find(i)) {
                cnt++;
            }
        }
        return cnt;
    }
    //统计联通块的个数
    int countConnected() {
        set<int> s;
        for (int i = 1; i <= f.size()-1; i++)
            s.insert(find(i));
        return s.size();
    }
    //a与b是否联通
    bool isConnect(int a, int b) {
        return find(a) == find(b);
    }
};
int main() {
    int n, m, a, b, c;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        if (n == 0) break;
        //1.先把给出的数据merge下，检测是否可以联通乘一个
        UnionFind uf(m);
        vector<vector<int>> e;
        for (int i = 0; i < n; i++) {
            cin >> a >> b >> c;
            e.push_back({a, b, c});
            uf.merge(a, b);
        }
        if (uf.countConnected() == 1) {
            //2.然后恢复并查集，克鲁斯卡尔选择最小生成树的成本
            uf = UnionFind(m);
            sort(e.begin(), e.end(), [](auto a, auto b) {
                return a[2] < b[2];
            });
            // for_each(e.begin(), e.end(), [](auto a) {
            //     cout << a[0] << " " << a[1] << " " << a[2] << endl;
            // });
            int cnt = 0, p = 0, ans = 0;
            while (cnt < m - 1) {
                if (!uf.isConnect(e[p][0], e[p][1])) {
                    uf.merge(e[p][0], e[p][1]);
                    ans += e[p][2];
                    cnt++;
                }
                p++;
            }
            cout << ans << endl;
        } else
            cout << "?" << endl;

    }
}
// 64 位输出请用 printf("%lld")