SyntaxPilot
Courses/Competitive Programming/Lesson 48
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 48 of 90

Minimum spanning tree problems

queued

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

  1. Sort the cables by cost.
  2. Go through them in order. If the two ends are in different DSU groups, take the cable and unite them; otherwise the cable would close a loop: skip it.
  3. 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

  1. 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.
  2. 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.
  3. 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).
  4. 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).
  5. 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.
  6. 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, unite if different groups, skip loops; check used == n − 1 (else -1, not 12); total in long 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, not 21.
  • 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