Connecting Cities With Minimum Cost

medium graph minimum spanning tree union find

Problem

There are n cities numbered from 1 to n. You are given connections, where each connections[i] = [a, b, cost] describes a bidirectional connection between cities a and b with the given cost. Return the minimum cost to connect all cities so that every city is reachable from every other city. If that is impossible, return -1.

Inputn = 4, connections = [[1,2,3],[3,4,4],[1,4,1],[2,3,6]]

Output8

Choosing edges 1-4 (1), 1-2 (3) and 3-4 (4) connects all 4 cities for a total of 8. The edge 2-3 (6) is skipped because it would form a cycle.

n (cities)

connections — "a b cost" per edge, ; separated

def minimum_cost(n, connections):
    parent = list(range(n + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    connections.sort(key=lambda e: e[2])
    total, used = 0, 0
    for a, b, cost in connections:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            total += cost
            used += 1
    return total if used == n - 1 else -1

function minimumCost(n, connections) {
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }
  connections.sort((a, b) => a[2] - b[2]);
  let total = 0, used = 0;
  for (const [a, b, cost] of connections) {
    const ra = find(a), rb = find(b);
    if (ra !== rb) {
      parent[ra] = rb;
      total += cost;
      used++;
    }
  }
  return used === n - 1 ? total : -1;
}

class Solution {
    int[] parent;
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    public int minimumCost(int n, int[][] connections) {
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        int total = 0, used = 0;
        for (int[] e : connections) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra != rb) {
                parent[ra] = rb;
                total += e[2];
                used++;
            }
        }
        return used == n - 1 ? total : -1;
    }
}

vector<int> parent;
int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}
int minimumCost(int n, vector<vector<int>>& connections) {
    parent.resize(n + 1);
    for (int i = 0; i <= n; i++) parent[i] = i;
    sort(connections.begin(), connections.end(),
         [](auto& a, auto& b){ return a[2] < b[2]; });
    int total = 0, used = 0;
    for (auto& e : connections) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra != rb) {
            parent[ra] = rb;
            total += e[2];
            used++;
        }
    }
    return used == n - 1 ? total : -1;
}

Explanation

We want the cheapest set of roads that connects every city — a classic minimum spanning tree. This solution uses Kruskal's algorithm: keep adding the cheapest road that doesn't create a redundant loop.

First we sort all connections by cost. Then we walk through them from cheapest to most expensive. Union-find tracks which cities are already in the same connected group: find returns a city's group root, and joining two different roots merges their groups.

For each edge, if its two cities are already connected (same root), adding it would just form a cycle, so we skip it. Otherwise we take the edge, add its cost to total, and increment used.

A tree over n cities needs exactly n-1 edges. If we end with fewer, the graph can't be fully connected, so we return -1. Example: n=4, [[1,2,3],[3,4,4],[1,4,1],[2,3,6]] picks 1-4(1), 1-2(3), 3-4(4) for total 8, skipping 2-3(6) as a cycle.

Time: O(E log E) Space: O(n)