Crack the Backend

Problem Statement

You have n nodes labeled 0 to n-1 and a list of undirected edges edges[i] = [u, v]. Return the number of connected components in the graph after adding all edges. (No duplicate edges.)

Key Observations

Union Find (Disjoint Set): Start with n components (each node is its own root). For each edge (u, v), union the sets containing u and v; the number of components decreases when two different sets merge. After processing all edges, the number of roots (nodes i with find(i) == i) is the number of connected components.

Approach

High-level: UF of size n. For each (u,v): union(u,v). Return count of i such that find(i) == i.

Steps: int[] parent = new int[n]; for (i=0;i<n;i++) parent[i]=i; for (int[] e : edges) union(e[0], e[1]); int count = 0; for (int i=0;i<n;i++) if (find(i)==i) count++; return count;

Implementation

Java

int[] parent;
void union(int a, int b) { parent[find(a)] = find(b); }
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }

public int countComponents(int n, int[][] edges) {
    parent = new int[n];

    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    for (int[] e : edges) {
        union(e[0], e[1]);
    }

    int count = 0;

    for (int i = 0; i < n; i++) {
        if (parent[i] == i) {
            count++;
        }
    }

    return count;
}

Test Cases

Example 1

Input

n = 5, edges = [[0,1],[1,2],[3,4]]

Expected

2

Explanation

Two components: {0,1,2} and {3,4}.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.