# GRL_2_A Minimum Spanning Tree (Kruskal)

AOJ

Table of contents

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A

# # Computational complexity

$O(ElogE)$ (for sorting edges)

# # Solution

#define MAX_N 10001
#define W_INF (1 << 21)

class Edge {
public:
Int src, tgt, cost;
Edge(Int src, Int tgt, Int cost): src(src), tgt(tgt), cost(cost) {}

bool operator < ( const Edge &e) const {
return cost < e.cost;
}
};

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

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

void unite(int x, int y) {
x = root(x), y = root(y);
if (rank[x] > rank[y]) {
parent[y] = x;
} else {
parent[x] = y;
if (rank[x] == rank[y]) rank[y]++;
}
}

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

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

return parent[x];
}
};

Int N;
vector<Edge> edges;

Int kruskal() {
Int total = 0;
sort(edges.begin(), edges.end());
DisjointSet dset(N);
for (auto edge: edges) {
if (!dset.same(edge.src, edge.tgt)) {
total += edge.cost;
dset.unite(edge.src, edge.tgt);
}
}
return total;
}

int main(void) {
int e, u, v, w;
cin >> N >> e;
while (cin >> u >> v >> w) {
edges.push_back(Edge(u, v, w));
}

cout << kruskal() << endl;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!