Graph/Kruskal.cpp

• View this file on GitHub
• Last update: 2021-06-16 21:34:35+09:00

Depends on

• Union-Find (DataStructure/UnionFind.cpp)

Verified with

• Test/AOJ/Kruskal.test.cpp

Code

#include"../DataStructure/UnionFind.cpp"

struct edge {
    int u,v;
    long long cost;

    bool operator<(const edge& b) const {
        return cost < b.cost;
    }
};

int N,M;
edge graph[200010];

long long Kruskal() {
    sort(graph,graph + M);
    UnionFind uf(N);
    long long ret = 0;
    for(int i = 0;i < M;i++) {
        edge e = graph[i];
        if(!uf.same(e.u,e.v)) {
            uf.unite(e.u,e.v);
            ret += e.cost;
        }
    }
    return ret;
}

#line 1 "DataStructure/UnionFind.cpp"
class UnionFind {
    vector<int> par;
    vector<int> siz;

public:

    UnionFind(int n) {
        par.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }

    int find(int x) {
        if(par[x] == x) {
            return x;
        }
        else {
            return par[x] = find(par[x]);
        }
    }

    void unite(int x,int y) {
        x = find(x);
        y = find(y);
        if(x == y) {
            return;
        }
        if(siz[x] < siz[y]) {
            swap(x,y);
        }
        par[y] = x;
        siz[x] += siz[y];
    }

    bool same(int x,int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return siz[find(x)];
    }
};
#line 2 "Graph/Kruskal.cpp"

struct edge {
    int u,v;
    long long cost;

    bool operator<(const edge& b) const {
        return cost < b.cost;
    }
};

int N,M;
edge graph[200010];

long long Kruskal() {
    sort(graph,graph + M);
    UnionFind uf(N);
    long long ret = 0;
    for(int i = 0;i < M;i++) {
        edge e = graph[i];
        if(!uf.same(e.u,e.v)) {
            uf.unite(e.u,e.v);
            ret += e.cost;
        }
    }
    return ret;
}

Back to top page