1.Problem
https://cses.fi/problemset/task/1675
2.Idea
Standard MST with UnionFind implementation
3.Source
int n, m;
struct Edge {
int u, v, c;
bool operator < (const Edge &a)const {
return c < a.c;
}
} Edges[N];
struct UF {
vector<int> Parent;
vector<int> Size;
int Count;
void init(int n) {
Count = n;
Parent.resize(n);
Size.resize(n);
REP(i, n) {
make_set(i);
}
}
void make_set(int v) {
Parent[v] = v;
Size[v] = 1;
}
int find_set(int v) {
if (v == Parent[v])
return v;
return Parent[v] = find_set(Parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (Size[a] < Size[b])
swap(a, b);
Count--;
Parent[b] = a;
Size[a] += Size[b];
}
}
};
void solve()
{
cin >> n >> m;
REP(i, m) {
cin >> Edges[i].u >> Edges[i].v >> Edges[i].c;
Edges[i].u--;
Edges[i].v--;
}
sort(Edges, Edges + m);
UF uf;
uf.init(n);
Int ret = 0;
REP(i, m) {
int u = Edges[i].u;
int v = Edges[i].v;
int c = Edges[i].c;
if (uf.find_set(u) != uf.find_set(v)) {
ret += c;
uf.union_sets(u, v);
}
}
if (uf.Count == 1) cout << ret << endl;
else cout << "IMPOSSIBLE" << endl;
}
