Theory
Implementation
#include <bits/stdc++.h>
using namespace std;
// Disjoint-Set Union
class DSU {
private:
vector<int> parent;
vector<int> size;
public:
DSU(int n) {
parent.resize(n + 1);
iota(begin(parent), end(parent), 0);
size.resize(n + 1);
fill(begin(size), end(size), 1);
}
int root(int x) {
while (x != parent[x]) {
// Path compression
x = parent[parent[x]];
}
return x;
}
bool connected(int p, int q) {
return root(p) == root(q);
}
void join(int p, int q) {
p = root(p);
q = root(q);
if (size[p] <= size[q]) {
parent[p] = q;
size[q] += size[p];
} else {
parent[q] = p;
size[p] += size[q];
}
}
};
struct Edge {
int w, u, v;
bool operator<(const Edge& that) const {
return w < that.w;
}
};
class Kruskal {
public:
int mst(vector<Edge> edges, int n) {
sort(begin(edges), end(edges));
DSU dsu(n);
int ans = 0;
for (auto edge : edges) {
if (dsu.connected(edge.u, edge.v)) { continue; }
dsu.join(edge.u, edge.v);
ans += edge.w;
}
return ans;
}
};
Practice problems