These are the notes for Competitive Programming episode 48, the fourth episode of the graphs section. The DSU from episode 47 goes to work. Village Wi-Fi asks for the cheapest set of cables that connects every village: trying every subset of cables is correct but Time Limit Exceeded at only 40 cables (2^40 subsets). A careful contractor who signs the cheapest quote first and refuses any cable that would close a loop is Kruskal's algorithm: sort the edges, then unite with a DSU, O(m log m). Forgetting to check that n − 1 cables were used prints 12 where the answer is -1. The cut property explains why cheapest-first is always safe. Dish or Cable lets a village buy its own satellite dish: "cable MST + one cheapest dish" prints 21 where 16 is right, and a virtual node (village 0, the satellite) turns every dish into an ordinary cable. Street Lamps can wire any two lamps (cost = Manhattan distance): Kruskal would need 5 · 10^7 edges (TLE), and Prim's algorithm in O(n²) needs only one array. Three stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
A contractor must bring Wi-Fi to every village in a district. He has a pile of quotes, one per possible cable, and he sorts them, cheapest on top. He takes the top quote: if it links two villages that can't yet reach each other, he signs it; if the two villages are already connected through cables he has signed, the new cable would only make a loop, so he throws the quote away. When n − 1 quotes are signed, every village is connected. He never regrets a signature, and the reason is the cut property below.
For the street lamps, an electrician works differently: he grows one circuit, always wiring the lamp that is closest to the circuit so far, and for every other lamp he only remembers one number, its shortest possible wire to the circuit.
Problem M1 · Village Wi-Fi
(Written for this course, in the style of an AtCoder Beginner Contest problem.)
n villages, m possible cables; cable i joins a_i and b_i and costs w_i. Choose cables so that every village can reach every other one, with minimum total cost. Print that cost, or −1 if it is impossible.
- Input: n and m (1 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a_i b_i w_i (1 ≤ w_i ≤ 10^9).
- Output: the minimum total cost, or −1.
| Input | Output |
|---|---|
4 5 / 1 2 3 / 2 3 1 / 3 4 4 / 1 4 2 / 1 3 5 |
6 (cables 2–3, 1–4, 1–2) |
4 2 / 1 2 5 / 3 4 7 |
-1 |
1 0 |
0 |
The answer is a tree. If the chosen cables contained a loop, removing the most expensive cable of the loop would keep everything connected and cost no more. A connected set of cables with no loop is a tree, and a tree on n villages has exactly n − 1 edges. The cheapest one is the minimum spanning tree (MST): "spanning" because it reaches every node.
The obvious attempt: every subset of cables (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m); // (a, b, cost)
for (auto &[a, b, w] : e) cin >> a >> b >> w;
ll best = -1;
for (ll mask = 0; mask < (1LL << m); mask++) { // every subset of cables
vector<int> p(n + 1);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); };
ll cost = 0;
int parts = n;
for (int i = 0; i < m; i++)
if (mask >> i & 1) {
auto [a, b, w] = e[i];
cost += w;
if (find(a) != find(b)) { p[find(a)] = find(b); parts--; }
}
if (parts == 1 && (best == -1 || cost < best)) best = cost;
}
cout << best << "\n";
}
6
With only 40 cables (built inside the program):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 30, m = 40; // only 40 cables, built here
vector<array<int, 3>> e(m); // (a, b, cost)
mt19937 rng(48);
for (auto &[a, b, w] : e) a = rng() % n + 1, b = rng() % n + 1, w = rng() % 100 + 1;
ll best = -1;
for (ll mask = 0; mask < (1LL << m); mask++) { // every subset of cables
vector<int> p(n + 1);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) { return p[x] == x ? x : p[x] = find(p[x]); };
ll cost = 0;
int parts = n;
for (int i = 0; i < m; i++)
if (mask >> i & 1) {
auto [a, b, w] = e[i];
cost += w;
if (find(a) != find(b)) { p[find(a)] = find(b); parts--; }
}
if (parts == 1 && (best == -1 || cost < best)) best = cost;
}
cout << best << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
2^40 ≈ 1.1 · 10^12 subsets. The real limit is m = 2 · 10^5.
Kruskal's algorithm
- Sort the cables by cost.
- Go through them in order. If the two ends are in different DSU groups, take the cable and
unitethem; otherwise the cable would close a loop: skip it. - If n − 1 cables were taken, the total is the answer; otherwise the graph is not connected: −1.
| Cable (cost) | Groups before | Taken? | Total |
|---|---|---|---|
| 2–3 (1) | {1} {2} {3} {4} | yes | 1 |
| 1–4 (2) | {1} {2, 3} {4} | yes | 3 |
| 1–2 (3) | {1, 4} {2, 3} | yes | 6 |
| 3–4 (4) | {1, 2, 3, 4} | no (loop) | 6 |
| 1–3 (5) | {1, 2, 3, 4} | no (loop) | 6 |
Storing each cable as (cost, a, b) makes sort order by cost with no comparator. The DSU's unite returns false when both ends already share a root.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m); // (cost, a, b): sorts by cost
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.begin(), e.end()); // cheapest first
DSU d(n);
ll total = 0;
int used = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) { // skip cables that close a loop
total += w;
used++;
}
cout << (used == n - 1 ? total : -1) << "\n"; // not all connected → −1
}
6
-1
0
The forgotten connectivity check
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m); // (cost, a, b): sorts by cost
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.begin(), e.end()); // cheapest first
DSU d(n);
ll total = 0;
int used = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) { // skip cables that close a loop
total += w;
used++;
}
cout << total << "\n";
}
12
Expected -1: only 2 of the 3 needed cables were taken, so the villages {1, 2} and {3, 4} are still apart.
The worst case and long long
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
int n = 200000, m = 200000; // worst case, built here
mt19937 rng(48);
vector<array<int, 3>> e;
for (int v = 2; v <= n; v++) e.push_back({int(rng() % 1000000000) + 1, v, int(rng() % (v - 1)) + 1});
while ((int)e.size() < m) e.push_back({int(rng() % 1000000000) + 1, int(rng() % n) + 1, int(rng() % n) + 1});
sort(e.begin(), e.end());
DSU d(n);
ll total = 0;
int used = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) { total += w; used++; }
cout << (used == n - 1 ? total : -1) << "\n";
}
95105656279104
About 10^14: up to 2 · 10^5 − 1 cables of 10^9 each, so the total must be long long.
Why cheapest-first is safe: the cut property
A cut splits the villages into two non-empty sides A and B. Every spanning tree must use at least one cable crossing the cut (otherwise A and B would not be connected).
Cut property. For any cut, a cheapest crossing cable e belongs to some minimum spanning tree.
Proof (exchange argument). Take an MST T that does not contain e. Adding e to T creates exactly one loop, and that loop crosses the cut at e, so it must cross back somewhere else, at a cable f. Remove f: the result is still a spanning tree, and it costs cost(T) − cost(f) + cost(e) ≤ cost(T), because e was a cheapest crossing cable. So there is an MST containing e. ∎
Why Kruskal is correct. When Kruskal takes cable (a, b), take the cut "a's current group | everything else". Every cheaper cable has already been looked at and either joined groups or lay inside one, so none of them crosses this cut; (a, b) is a cheapest crossing cable, and by the cut property taking it is safe. This is the same exchange argument as the greedy proofs of episode 14.
Stress test against every subset
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
ll kruskal(int n, vector<array<int, 3>> e) { // e: (cost, a, b)
sort(e.begin(), e.end());
DSU d(n);
ll total = 0;
int used = 0;
for (auto [w, a, b] : e) if (d.unite(a, b)) total += w, used++;
return used == n - 1 ? total : -1;
}
ll brute(int n, vector<array<int, 3>> &e) {
int m = e.size();
ll best = -1;
for (int mask = 0; mask < (1 << m); mask++) {
DSU d(n);
ll cost = 0;
int parts = n;
for (int i = 0; i < m; i++) if (mask >> i & 1) { cost += e[i][0]; if (d.unite(e[i][1], e[i][2])) parts--; }
if (parts == 1 && (best == -1 || cost < best)) best = cost;
}
return best;
}
int main() {
mt19937 rng(48);
for (int t = 1; t <= 500; t++) {
int n = rng() % 5 + 1, m = rng() % 9;
vector<array<int, 3>> e(m);
for (auto &[w, a, b] : e) w = rng() % 10 + 1, a = rng() % n + 1, b = rng() % n + 1;
if (kruskal(n, e) != brute(n, e)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem M2 · Dish or Cable
(Written for this course, in the style of a Codeforces Div. 2 D problem.)
Same villages and cables. In addition, village i can buy its own satellite dish for dish_i. Every village needs internet: either its own dish, or a cable path to some village with a dish. Print the minimum total cost.
- Input: n and m, then dish_1 … dish_n, then m cables a b w (all costs ≤ 10^9).
- Output: the minimum total cost (it always exists: every village can buy a dish).
| Input | Output |
|---|---|
4 3 / 5 9 9 5 / 1 2 3 / 2 3 10 / 3 4 3 |
16 (dishes at 1 and 4, cables 1–2 and 3–4) |
3 0 / 4 1 6 |
11 (three dishes) |
3 2 / 1 50 50 / 1 2 2 / 2 3 2 |
5 (one dish, two cables) |
The obvious attempt: cable MST + one cheapest dish (WA)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<ll> dish(n + 1);
for (int i = 1; i <= n; i++) cin >> dish[i];
vector<array<ll, 3>> e(m); // (cost, a, b)
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.begin(), e.end());
DSU d(n);
ll total = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) total += w; // MST of the cables
total += *min_element(dish.begin() + 1, dish.end()); // plus one cheapest dish
cout << total << "\n";
}
21
It paid 10 for the middle cable when a second dish costs only 5. The number of dishes is part of the decision.
The virtual node
Add an imaginary village 0, the satellite, and for every i a cable 0–i costing dish_i. "Village i has internet" now means "village i is connected to village 0". So the answer is exactly the MST of the n + 1 villages 0 … n, and it always exists. Kruskal picks 3 (1–2), 3 (3–4), 5 (0–1), 5 (0–4): 16.
The same trick handles "build a well or pipe water", "open a shop or deliver from a neighbour", and multi-source problems in general: a choice that "starts from nothing" becomes an edge to a virtual node.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<ll> dish(n + 1);
for (int i = 1; i <= n; i++) cin >> dish[i];
vector<array<ll, 3>> e(m); // (cost, a, b)
for (auto &[w, a, b] : e) cin >> a >> b >> w;
for (int i = 1; i <= n; i++)
e.push_back({dish[i], 0, i}); // village 0 = the satellite
sort(e.begin(), e.end());
DSU d(n); // DSU covers 0..n
ll total = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) total += w;
cout << total << "\n"; // always connected through 0
}
16
11
5
Stress test: try every set of dish villages
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
ll fast(int n, vector<ll> dish, vector<array<ll, 3>> e) {
for (int i = 1; i <= n; i++) e.push_back({dish[i], 0, i});
sort(e.begin(), e.end());
DSU d(n);
ll total = 0;
for (auto [w, a, b] : e) if (d.unite(a, b)) total += w;
return total;
}
ll brute(int n, vector<ll> &dish, vector<array<ll, 3>> &e) { // which villages get a dish?
ll best = LLONG_MAX;
for (int s = 1; s < (1 << n); s++) {
ll cost = 0;
DSU d(n);
for (int i = 0; i < n; i++) if (s >> i & 1) cost += dish[i + 1], d.unite(0, i + 1);
vector<array<ll, 3>> f = e;
sort(f.begin(), f.end());
for (auto [w, a, b] : f) if (d.unite(a, b)) cost += w;
bool ok = true;
for (int i = 1; i <= n; i++) ok &= d.find(i) == d.find(0);
if (ok) best = min(best, cost);
}
return best;
}
int main() {
mt19937 rng(48);
for (int t = 1; t <= 500; t++) {
int n = rng() % 5 + 1, m = rng() % 7;
vector<ll> dish(n + 1);
for (int i = 1; i <= n; i++) dish[i] = rng() % 20 + 1;
vector<array<ll, 3>> e(m);
for (auto &[w, a, b] : e) w = rng() % 20 + 1, a = rng() % n + 1, b = rng() % n + 1;
if (fast(n, dish, e) != brute(n, dish, e)) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Problem M3 · Street Lamps
(Written for this course.)
n street lamps at integer points (x_i, y_i). Any two lamps can be wired; the cost is the Manhattan distance |x_i − x_j| + |y_i − y_j|. Connect all lamps at minimum total cost.
- Input: n (1 ≤ n ≤ 10^4), then n lines x_i y_i (0 ≤ x_i, y_i ≤ 10^6).
- Output: the minimum total cost.
| Input | Output |
|---|---|
4 / 0 0 / 2 2 / 3 10 / 5 2 |
16 (wires of 3, 4 and 9) |
1 / 7 7 |
0 |
The obvious attempt: Kruskal on every pair (TLE)
A complete graph has n(n − 1)/2 edges: 5 · 10^7 for n = 10^4, which is 1.2 GB as array<ll, 3>, plus a sort of 5 · 10^7 items:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
int n = 10000; // worst case, built here
vector<ll> x(n), y(n);
mt19937 rng(48);
for (int i = 0; i < n; i++) x[i] = rng() % 1000000, y[i] = rng() % 1000000;
auto cost = [&](int i, int j) { return llabs(x[i] - x[j]) + llabs(y[i] - y[j]); };
vector<array<ll, 3>> e; // every pair: n(n − 1)/2 edges
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) e.push_back({cost(i, j), i, j});
sort(e.begin(), e.end());
DSU d(n);
ll total = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) total += w;
cout << total << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
Prim's algorithm in O(n²)
Grow one tree from lamp 0. Keep best[v] = the cheapest wire from the tree to lamp v (∞ at first, 0 for lamp 0). Repeat n times: take the lamp u outside the tree with the smallest best[u], add it (paying best[u]), and update best[v] = min(best[v], cost(u, v)) for every lamp v still outside. Each round is O(n), so the total is O(n²) with O(n) memory and no edge list. It is correct by the cut property with the cut "tree | the rest": the lamp taken is joined by a cheapest crossing wire.
Prim with a binary heap is O(m log n), better for sparse graphs; for dense graphs (m ≈ n²), the plain O(n²) version is faster and simpler.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> x(n), y(n);
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
auto cost = [&](int i, int j) { return llabs(x[i] - x[j]) + llabs(y[i] - y[j]); };
vector<ll> best(n, LLONG_MAX); // cheapest wire from the tree to v
vector<bool> in(n, false);
best[0] = 0;
ll total = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int v = 0; v < n; v++) // the closest lamp not yet in the tree
if (!in[v] && (u == -1 || best[v] < best[u])) u = v;
in[u] = true;
total += best[u];
for (int v = 0; v < n; v++) // u is in: update everyone else
if (!in[v]) best[v] = min(best[v], cost(u, v));
}
cout << total << "\n";
}
16
0
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 10000; // worst case, built here
vector<ll> x(n), y(n);
mt19937 rng(48);
for (int i = 0; i < n; i++) x[i] = rng() % 1000000, y[i] = rng() % 1000000;
auto cost = [&](int i, int j) { return llabs(x[i] - x[j]) + llabs(y[i] - y[j]); };
vector<ll> best(n, LLONG_MAX); // cheapest wire from the tree to v
vector<bool> in(n, false);
best[0] = 0;
ll total = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int v = 0; v < n; v++) // the closest lamp not yet in the tree
if (!in[v] && (u == -1 || best[v] < best[u])) u = v;
in[u] = true;
total += best[u];
for (int v = 0; v < n; v++) // u is in: update everyone else
if (!in[v]) best[v] = min(best[v], cost(u, v));
}
cout << total << "\n";
}
81296665
About half a second for 10^4 lamps (10^8 simple steps).
Stress test: Prim against Kruskal
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
mt19937 rng(48);
for (int t = 1; t <= 500; t++) {
int n = rng() % 30 + 1;
vector<ll> x(n), y(n);
for (int i = 0; i < n; i++) x[i] = rng() % 100, y[i] = rng() % 100;
auto cost = [&](int i, int j) { return llabs(x[i] - x[j]) + llabs(y[i] - y[j]); };
vector<array<ll, 3>> e;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) e.push_back({cost(i, j), i, j});
sort(e.begin(), e.end());
DSU d(n);
ll k = 0;
for (auto [w, a, b] : e) if (d.unite(a, b)) k += w;
vector<ll> best(n, LLONG_MAX);
vector<bool> in(n, false);
best[0] = 0;
ll p = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int v = 0; v < n; v++) if (!in[v] && (u == -1 || best[v] < best[u])) u = v;
in[u] = true;
p += best[u];
for (int v = 0; v < n; v++) if (!in[v]) best[v] = min(best[v], cost(u, v));
}
if (k != p) { cout << "mismatch on test " << t; return 0; }
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Time | Memory | Verdict |
|---|---|---|---|
| every subset of cables | O(2^m · m) | O(n) | TLE at m = 40 |
| Kruskal (sort + DSU) | O(m log m) | O(n + m) | accepted for m = 2 · 10^5, milliseconds |
| Kruskal + virtual node | O((m + n) log(m + n)) | O(n + m) | accepted |
| Kruskal on a complete graph | O(n² log n) | O(n²): 1.2 GB at n = 10^4 | TLE / MLE |
| Prim with a heap | O(m log n) | O(n + m) | good for sparse graphs |
| Prim with an array | O(n²) | O(n) | accepted for complete graphs, 0.55 s at n = 10^4 |
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| try every subset | Time Limit Exceeded |
2^m subsets | Kruskal |
no used == n - 1 check |
12 (expected -1) |
the graph was not connected | count the cables taken |
int total |
negative or wrapped totals | up to 2 · 10^14 | long long total |
| cable MST + one cheapest dish | 21 (expected 16) |
the number of dishes is a choice | virtual node 0 with edges 0–i |
| DSU of size n with a node 0 | out of bounds / wrong groups | node 0 needs a slot | DSU over 0..n |
| Kruskal on all pairs | Time Limit Exceeded |
5 · 10^7 edges | Prim O(n²) |
sorting (a, b, cost) arrays |
wrong order (by a, not by cost) | sort compares the first field first |
store (cost, a, b) |
| shortest-path tree instead of MST | Wrong Answer | different goal: distances from one node vs total cost | Kruskal / Prim |
Mini project
Write an MST toolbox with kruskal(n, edges), prim_dense(n, cost) and withVirtual(n, ownCost, edges), each returning the total and the list of chosen edges. Visualise the chosen edges for 20 random points (draw them as ASCII on a 40 × 20 grid, or print them as coordinate pairs). Then measure the time of Kruskal-on-all-pairs vs Prim-dense for n = 1000, 2000, 4000, 8000 and find where Kruskal stops being practical. Stress test all three against a brute force on tiny inputs.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Maximum spanning tree. Same input as Village Wi-Fi; maximise the total cost instead.
Solution
Sort in decreasing order and run Kruskal unchanged (the cut property works with "most expensive crossing edge"). Equivalently, negate every cost.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m);
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.rbegin(), e.rend()); // most expensive first
DSU d(n);
ll total = 0;
int used = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) { total += w; used++; }
cout << (used == n - 1 ? total : -1) << "\n";
}
The episode's samples:
12
-1
2. Forced cables. Some cables (flag 1) must be bought. Minimise the total cost of a connected network that contains them all.
Solution
Take every forced cable first (unite their ends and pay, even if one closes a loop), then run Kruskal on the rest. The cut property still applies to the remaining choices, because the forced cables only merge groups before we start.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<array<int, 4>> e(m); // (forced? 0 first, cost, a, b)
for (auto &[f, w, a, b] : e) { cin >> a >> b >> w >> f; f = !f; } // input flag 1 = forced → key 0
sort(e.begin(), e.end()); // forced cables first, then by cost
DSU d(n);
ll total = 0;
int used = 0;
for (auto [f, w, a, b] : e) {
bool joined = d.unite(a, b);
if (f == 0) { total += w; used += joined; } // a forced cable is paid even if it closes a loop
else if (joined) { total += w; used++; }
}
cout << (used == n - 1 ? total : -1) << "\n";
}
Input lines a b w flag. The Wi-Fi sample with 1–3 (cost 5) forced: 5 + 1 + 2 = 8. And three villages with two forced cables of 5 and an optional cable of 1, which is not needed:
8
10
3. Minimise the most expensive cable. Connect all villages so that the most expensive cable used is as cheap as possible. Print that cost, or −1.
Solution
The MST also minimises the largest edge (a minimum bottleneck spanning tree): Kruskal takes edges in increasing order and stops as soon as everything is connected, so the last edge it takes is the smallest possible maximum. (Binary search on the answer plus a connectivity check, from episode 11, also works.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m);
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.begin(), e.end());
DSU d(n);
int used = 0, worst = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) {
used++;
worst = w; // the last cable Kruskal takes is the largest in the MST
if (used == n - 1) break;
}
cout << (used == n - 1 ? worst : -1) << "\n";
}
3
-1
4. Exactly k groups. Choose cables so that the villages form exactly k groups, at minimum total cost.
Solution
Run Kruskal and stop after n − k successful unions: each union reduces the number of groups by one. This is single-linkage clustering: it is the MST with its k − 1 most expensive edges removed.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
int n, m, k;
cin >> n >> m >> k; // end with exactly k groups
vector<array<int, 3>> e(m);
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.begin(), e.end());
DSU d(n);
ll total = 0;
int groups = n;
for (auto [w, a, b] : e) {
if (groups == k) break; // stop early: n − k cables
if (d.unite(a, b)) { total += w; groups--; }
}
cout << (groups == k ? total : -1) << "\n";
}
Input n m k. The Wi-Fi sample with k = 2 (cables 1 and 2: 3), and three villages with no cables and k = 1:
3
-1
Quick quiz
Kruskal on 6 villages and 9 possible cables, and all villages can be connected. How many cables does it take?
if (d.unite(a, b)) { total += w; used++; }
A) 3 · B) 5 · C) 6 · D) 9
Answer
B. A spanning tree on n nodes always has exactly n − 1 = 5 edges; any extra cable would close a loop and be skipped.
Interview questions
- What is a minimum spanning tree? A set of n − 1 edges that connects all n nodes with the minimum total weight. It has no cycles.
- Explain Kruskal's algorithm and its complexity. Sort edges by weight, add each edge whose endpoints are in different DSU components. O(m log m) for the sort plus almost O(m) for the DSU.
- Explain Prim's algorithm. Grow one tree from a start node, always adding the cheapest edge leaving it. O(n²) with an array (dense graphs), O(m log n) with a heap (sparse graphs).
- Why is the greedy choice correct? The cut property: for any cut, a lightest crossing edge belongs to some MST (exchange argument: swap it with the other crossing edge on the cycle it creates).
- How do you handle "a node may pay its own cost instead of connecting"? Add a virtual node and an edge from it to every node with that cost, then take the MST.
- Is the MST unique? Yes if all edge weights are distinct; with equal weights there can be several MSTs, but they all have the same total weight (and the same multiset of weights).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Spanning tree | A set of edges that connects all nodes with no cycle; n − 1 edges | cables 2–3, 1–4, 1–2 |
| Minimum spanning tree (MST) | A spanning tree with the least total weight | total 6 |
| Cycle (loop) | A path that returns to its start | 1–2–3–1 |
| Tree | A connected graph with no cycle | n nodes, n − 1 edges |
| Kruskal's algorithm | Sort edges, add each one that joins two different components | Village Wi-Fi |
| Prim's algorithm | Grow one tree, always adding the cheapest edge leaving it | Street Lamps |
| DSU (union–find) | Keeps the components while edges are added | d.unite(a, b) |
| Cut | A split of the nodes into two non-empty sides | {1, 4} vs {2, 3} |
| Crossing edge | An edge with one end on each side of a cut | 1–2 for the cut above |
| Cut property | A lightest crossing edge of any cut is in some MST | why Kruskal and Prim are correct |
| Exchange argument | Proving a greedy choice by swapping it into an optimal answer | add e, remove f |
| Virtual node | An imaginary node that turns a special choice into ordinary edges | village 0, the satellite |
| Complete graph | Every pair of nodes is joined by an edge | n(n − 1)/2 edges |
| Dense / sparse graph | m close to n² / m close to n | lamps / villages |
| Manhattan distance | |x₁ − x₂| + |y₁ − y₂| | (0, 0) to (2, 2): 4 |
| Bottleneck | The largest edge on a path or in a tree | 3 in the sample MST |
| Connected | Every node can reach every other | needed for the MST to exist |
array<int, 3> |
A fixed-size triple; compared field by field | (cost, a, b) sorts by cost |
long long |
64-bit integer for large totals | 95105656279104 |
| Brute force | Trying every possibility | every subset of cables |
| Stress test | Comparing a fast solution with a slow, surely-correct one on random inputs | all 500 tests passed |
| Single-linkage clustering | Stopping Kruskal at k components | homework 4 |
| Time Limit Exceeded / Wrong Answer | Too slow / wrong output | subsets: TLE; one dish: WA |
Summary
- The cheapest connected network is a tree with n − 1 edges: the MST.
- Every subset is 2^m: TLE at m = 40.
- Kruskal: sort by cost,
uniteif different groups, skip loops; check used == n − 1 (else-1, not12); total inlong long. O(m log m). - Cut property: the cheapest edge across any cut is safe; it proves Kruskal and Prim.
- "Build it yourself" costs → a virtual node with an edge to every node:
16, not21. - Complete graphs: Kruskal needs 5 · 10^7 edges (TLE); Prim in O(n²) with one
best[]array: 0.55 s at n = 10^4.
Solutions in C++, Java and Python
Problem M1 · Village Wi-Fi
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<array<int, 3>> e(m); // (cost, a, b): sorts by cost
for (auto &[w, a, b] : e) cin >> a >> b >> w;
sort(e.begin(), e.end()); // cheapest first
DSU d(n);
ll total = 0;
int used = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) { // skip cables that close a loop
total += w;
used++;
}
cout << (used == n - 1 ? total : -1) << "\n"; // not all connected → −1
}
Java (iterative find with path halving: no recursion depth problem)
import java.io.*;
import java.util.*;
public class Main {
static int[] p, sz;
static int find(int x) {
while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } // path halving, no recursion
return x;
}
static boolean unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
p[b] = a; sz[a] += sz[b];
return true;
}
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
st.nextToken(); int m = (int) st.nval;
int[][] e = new int[m][3];
for (int i = 0; i < m; i++)
for (int j = 0; j < 3; j++) { st.nextToken(); e[i][j] = (int) st.nval; } // a b cost
Arrays.sort(e, (x, y) -> Integer.compare(x[2], y[2])); // cheapest first
p = new int[n + 1]; sz = new int[n + 1];
for (int i = 0; i <= n; i++) { p[i] = i; sz[i] = 1; }
long total = 0;
int used = 0;
for (int[] c : e)
if (unite(c[0], c[1])) { total += c[2]; used++; }
System.out.println(used == n - 1 ? total : -1);
}
}
6
-1
0
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
e = []
for i in range(m):
a, b, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
e.append((w, a, b))
e.sort() # cheapest first
p = list(range(n + 1))
sz = [1] * (n + 1)
def find(x):
while p[x] != x:
p[x] = p[p[x]] # path halving
x = p[x]
return x
total = used = 0
for w, a, b in e:
a, b = find(a), find(b)
if a == b:
continue # would close a loop
if sz[a] < sz[b]:
a, b = b, a
p[b] = a
sz[a] += sz[b]
total += w
used += 1
print(total if used == n - 1 else -1)
main()
6
-1
0
Problem M2 · Dish or Cable
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> p, sz;
DSU(int n) : p(n + 1), sz(n + 1, 1) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false; // already connected: a loop
if (sz[a] < sz[b]) swap(a, b);
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<ll> dish(n + 1);
for (int i = 1; i <= n; i++) cin >> dish[i];
vector<array<ll, 3>> e(m); // (cost, a, b)
for (auto &[w, a, b] : e) cin >> a >> b >> w;
for (int i = 1; i <= n; i++)
e.push_back({dish[i], 0, i}); // village 0 = the satellite
sort(e.begin(), e.end());
DSU d(n); // DSU covers 0..n
ll total = 0;
for (auto [w, a, b] : e)
if (d.unite(a, b)) total += w;
cout << total << "\n"; // always connected through 0
}
Java
import java.io.*;
import java.util.*;
public class Main {
static int[] p, sz;
static int find(int x) {
while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; }
return x;
}
static boolean unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
p[b] = a; sz[a] += sz[b];
return true;
}
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
st.nextToken(); int m = (int) st.nval;
long[][] e = new long[m + n][3]; // (cost, a, b)
for (int i = 1; i <= n; i++) { st.nextToken(); e[m + i - 1] = new long[]{(long) st.nval, 0, i}; } // village 0 = satellite
for (int i = 0; i < m; i++) {
st.nextToken(); long a = (long) st.nval;
st.nextToken(); long b = (long) st.nval;
st.nextToken(); long w = (long) st.nval;
e[i] = new long[]{w, a, b};
}
Arrays.sort(e, (x, y) -> Long.compare(x[0], y[0]));
p = new int[n + 1]; sz = new int[n + 1];
for (int i = 0; i <= n; i++) { p[i] = i; sz[i] = 1; }
long total = 0;
for (long[] c : e)
if (unite((int) c[1], (int) c[2])) total += c[0];
System.out.println(total);
}
}
16
11
5
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
e = [(int(data[1 + i]), 0, i) for i in range(1, n + 1)] # dish = cable to village 0
pos = 2 + n
for _ in range(m):
a, b, w = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
e.append((w, a, b))
e.sort()
p = list(range(n + 1))
def find(x):
while p[x] != x:
p[x] = p[p[x]]
x = p[x]
return x
total = 0
for w, a, b in e:
a, b = find(a), find(b)
if a != b:
p[a] = b
total += w
print(total)
main()
16
11
5
Problem M3 · Street Lamps
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<ll> x(n), y(n);
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
auto cost = [&](int i, int j) { return llabs(x[i] - x[j]) + llabs(y[i] - y[j]); };
vector<ll> best(n, LLONG_MAX); // cheapest wire from the tree to v
vector<bool> in(n, false);
best[0] = 0;
ll total = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int v = 0; v < n; v++) // the closest lamp not yet in the tree
if (!in[v] && (u == -1 || best[v] < best[u])) u = v;
in[u] = true;
total += best[u];
for (int v = 0; v < n; v++) // u is in: update everyone else
if (!in[v]) best[v] = min(best[v], cost(u, v));
}
cout << total << "\n";
}
Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken(); int n = (int) st.nval;
long[] x = new long[n], y = new long[n];
for (int i = 0; i < n; i++) {
st.nextToken(); x[i] = (long) st.nval;
st.nextToken(); y[i] = (long) st.nval;
}
long[] best = new long[n];
Arrays.fill(best, Long.MAX_VALUE);
boolean[] in = new boolean[n];
best[0] = 0;
long total = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int v = 0; v < n; v++)
if (!in[v] && (u == -1 || best[v] < best[u])) u = v;
in[u] = true;
total += best[u];
for (int v = 0; v < n; v++)
if (!in[v]) best[v] = Math.min(best[v], Math.abs(x[u] - x[v]) + Math.abs(y[u] - y[v]));
}
System.out.println(total);
}
}
16
0
Python (O(n²) in pure Python is fine for a few thousand lamps; use C++ for n = 10^4)
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(data[1 + 2 * i]) for i in range(n)]
y = [int(data[2 + 2 * i]) for i in range(n)]
INF = float('inf')
best = [INF] * n
inside = [False] * n
best[0] = 0
total = 0
for _ in range(n):
u = min((v for v in range(n) if not inside[v]), key=best.__getitem__) # closest lamp outside
inside[u] = True
total += best[u]
xu, yu = x[u], y[u]
for v in range(n):
if not inside[v]:
c = abs(xu - x[v]) + abs(yu - y[v])
if c < best[v]:
best[v] = c
print(total)
main()
16
0