EF-T09: Component count after each connection

Exercise contract#

Start with n isolated nodes labeled 0 through n-1. Process the undirected connections in order. After each connection, return the current number of connected components. A valid self-edge, repeated edge, or edge closing a cycle is a no-op. Reject a negative n, a connection that is not a pair, or an endpoint outside 0 through n-1.

Constraints

• 0 <= n <= 100,000.
• 0 <= connections.length <= 200,000.
• Every accepted connection contains exactly two integer node IDs in [0, n).
• The result contains one count for every accepted connection, including no-op connections.

Examples

n=6, connections=[(0,1),(1,2),(3,4),(2,4),(0,4)]

[5,4,3,2,2]The first four edges merge distinct components. The final edge connects nodes already represented by the same root.

n=3, connections=[(0,0),(0,1),(1,0)]

[3,2,2]The self-edge and repeated undirected connection do not change the component count.

Derive the approach#

Baseline: After each edge, rebuild adjacency for every edge seen so far and run a full DFS/BFS to recount components. This is correct but repeats O(n + e) work after each update.

1. Represent each component by a root. Initially every node is its own root and the component count is n.
2. For an incoming edge, find both roots. Equal roots mean the edge adds no connectivity, so append the unchanged count.
3. Otherwise attach the smaller tree below the larger root, decrement the count exactly once, and append it.
4. Compress paths during find so later representative queries reuse earlier work.

Time

O((n + m) α(n)) for m connections

Space

O(n) auxiliary space plus O(m) output

Assumptions

Endpoints are validated first; α is the inverse Ackermann bound for path compression with union by size, and integer counts fit the stated limits.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def component_counts(n, connections):
    if n < 0:
        raise ValueError("n must be nonnegative")
    parent = list(range(n))
    size = [1] * n
    components = n
    answer = []

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

    for edge in connections:
        if len(edge) != 2:
            raise ValueError("each connection must contain two endpoints")
        first, second = edge
        if not (0 <= first < n and 0 <= second < n):
            raise ValueError("endpoint outside node range")
        root_a, root_b = find(first), find(second)
        if root_a != root_b:
            if size[root_a] < size[root_b]:
                root_a, root_b = root_b, root_a
            parent[root_b] = root_a
            size[root_a] += size[root_b]
            components -= 1
        answer.append(components)
    return answer

import java.util.ArrayList;
import java.util.List;

static List<Integer> componentCounts(int n, int[][] connections) {
    if (n < 0) throw new IllegalArgumentException("n must be nonnegative");
    int[] parent = new int[n];
    int[] size = new int[n];
    for (int node = 0; node < n; node++) {
        parent[node] = node;
        size[node] = 1;
    }
    int components = n;
    List<Integer> answer = new ArrayList<>();
    for (int[] edge : connections) {
        if (edge == null || edge.length != 2) throw new IllegalArgumentException("connection must have two endpoints");
        int first = edge[0], second = edge[1];
        if (first < 0 || first >= n || second < 0 || second >= n) throw new IllegalArgumentException("endpoint outside node range");
        int rootA = find(parent, first), rootB = find(parent, second);
        if (rootA != rootB) {
            if (size[rootA] < size[rootB]) { int swap = rootA; rootA = rootB; rootB = swap; }
            parent[rootB] = rootA;
            size[rootA] += size[rootB];
            components--;
        }
        answer.add(components);
    }
    return answer;
}

static int find(int[] parent, int node) {
    while (parent[node] != node) {
        parent[node] = parent[parent[node]];
        node = parent[node];
    }
    return node;
}

Deterministic test plan#

Transfer and follow-ups#

• Return whether each connection actually merged two components.
• Track the size of the component containing a queried node after each update.

Explain why the component counter changes on successful union rather than on every edge.

Authorship and review#

An original instructional exercise built from standard disjoint-set operations; it is not attributed to an employer or claimed as a historical interview question.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09