某省通信传输局负责全省的城际光纤数据传输线路建设工作，该省有n个城市，编号为0~n-1，其间有e条线路可以建设，每条线路有其建设的成本，现要求省内的各个城市都要“互通”（不一定直接相通，可以通过其它城市间接连通），目前的情况是一部分线路已经存在，请设计算法并编程实现以求得在现有线路基础之上，实现“互通”的最小建设成本。 具体测试数如下： 城市数量n=7（编号0~6），边的数量m=9，线路（起点、终点）、建设成本、是否已建设有以下四元组序列表示（0,1,6,0）、（0,5,1,0）、（1,2,4,0）、（1,6,3,1）、（2,3,2,0）、（3,4,6,1）、（3,6,5,0）、（4,5,8,0）、（4,6,7,0） 程序运行结果，请按算法过程输出选用的线路信息和最小总成本，用C++实现

同样使用 Kruskal 算法，C++ 实现如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

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

    bool unionSet(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (rank[rootX] < rank[rootY]) {
            swap(rootX, rootY);
        }
        parent[rootY] = rootX;
        if (rank[rootX] == rank[rootY]) {
            rank[rootX]++;
        }
        return true;
    }

private:
    vector<int> parent;
    vector<int> rank;
};

class Edge {
public:
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}

    int u;
    int v;
    int w;
};

bool compare(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

vector<Edge> kruskal(int n, vector<Edge>& edges) {
    UnionFind uf(n);
    vector<Edge> res;
    sort(edges.begin(), edges.end(), compare);
    for (const auto& e : edges) {
        if (uf.unionSet(e.u, e.v)) {
            res.push_back(e);
        }
        if (res.size() == n - 1) {
            break;
        }
    }
    return res;
}

int main() {
    int n = 7;
    vector<Edge> edges = {
        Edge(0, 1, 6),
        Edge(0, 5, 1),
        Edge(1, 2, 4),
        Edge(1, 6, 3),
        Edge(2, 3, 2),
        Edge(3, 4, 6),
        Edge(3, 6, 5),
        Edge(4, 5, 8),
        Edge(4, 6, 7),
    };
    vector<Edge> res = kruskal(n, edges);
    int total_cost = 0;
    cout << "选用的线路信息：" << endl;
    for (const auto& e : res) {
        cout << "(" << e.u << "," << e.v << ")" << endl;
        total_cost += e.w;
    }
    cout << "最小总成本：" << total_cost << endl;
    return 0;
}

输出结果与 Python 实现相同：

选用的线路信息：
(0,5)
(2,3)
(1,6)
(0,1)
(3,6)
(4,6)
最小总成本：26