The implementation of Kruskal’s algorithm.

kruskal.cpp

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v;
    double weight;
    bool operator < (const Edge & e) const {
        return weight < e.weight;
    }
};

vector<Edge> edges;

struct UnionFind {
    // rank is the size of the tree!
    vector<int> father, rank;
    UnionFind(int size) {
        father.resize(size);
        rank.resize(size);

        for (int i = 0; i < size; i++) {
            father[i] = i;
            rank[i] = 1;
        }
    }

    int get_root(int u) {
        if (father[u] != u) {
            father[u] = get_root(father[u]);
        }
        return father[u];
    }

    bool is_unioned(int u, int v) {
        int ur = get_root(u);
        int vr = get_root(v);
        return ur == vr;
    }

    void union_(int u, int v) {
        int ur = get_root(u);
        int vr = get_root(v);
        // We merge ur to vr. Assure vr have bigger size, otherwise swap it!
        if (rank[ur] > rank[vr]) {
            swap(ur, vr);
        }

        father[ur] = vr;
        rank[vr] += rank[ur];
    }
};


int input() {
    int max_n = 0;
    int u, v;
    double w;
    while (scanf("(%d, %d) %lf\n", &u, &v, &w) > 0) {
        Edge e;
        e.u = u;
        e.v = v;
        e.weight = w;
        edges.push_back(e);
        max_n = max(max_n, max(u, v));
    }

    return max_n + 1;
}

int main() {
    //freopen("graph1.txt", "r", stdin);
    int max_n = input();
    sort(edges.begin(), edges.end());

    // krusal core
    UnionFind uf(max_n);
    double ans = 0;
    int added = 0;
    for (int i = 0; i < edges.size(); i++) {
        Edge &e = edges[i];
        if (!uf.is_unioned(e.u, e.v)) {
            uf.union_(e.u, e.v);
            ans += e.weight;
            added += 1;
        }
    }

    printf("Total %d nodes.\n", max_n);
    if (added == max_n - 1) {
        printf("The minimal weight sum is %lf\n", ans);
    } else {
        printf("There is no spining tree!\n");
    }
    return 0;
}