# Number of Connected Components in an Undirected Graph

- **Canonical ID**: `number-of-connected-components`
- **Canonical URL**: https://dsacheatsheet.com/problems/number-of-connected-components
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

## 1. Core Invariant / The Trick

Disjoint Set Union (DSU) with path compression + union-by-rank/size: initialize `components = n`, decrement `components` on every successful union between distinct roots.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(V + E * a(V))`
- **Space Complexity**: `O(V)`
- **Proof**: Inverse Ackermann amortized union/find runs effectively constant per edge; space holds only `parent` and `rank` arrays.

## 3. Minimal Idiomatic Code

### Python
```python
def countComponents(n: int, edges: list[list[int]]) -> int:
    parent = list(range(n))
    rank = [1] * n
    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    comp = n
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            if rank[ru] < rank[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            rank[ru] += rank[rv]
            comp -= 1
    return comp
```

### TypeScript
```typescript
export function countComponents(n: number, edges: number[][]): number {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Int32Array(n).fill(1);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  };
  let comp = n;
  for (const [u, v] of edges) {
    let ru = find(u), rv = find(v);
    if (ru !== rv) {
      if (rank[ru] < rank[rv]) [ru, rv] = [rv, ru];
      parent[rv] = ru;
      rank[ru] += rank[rv];
      comp--;
    }
  }
  return comp;
}
```

### C++
```cpp
int countComponents(int n, vector<vector<int>>& edges) {
    vector<int> p(n), sz(n, 1);
    iota(p.begin(), p.end(), 0);
    auto find = [&](int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; };
    int comp = n;
    for (auto& e : edges) {
        int a = find(e[0]), b = find(e[1]);
        if (a != b) { if (sz[a] < sz[b]) swap(a, b); p[b] = a; sz[a] += sz[b]; comp--; }
    }
    return comp;
}
```

### Java
```java
int countComponents(int n, int[][] edges) {
    int[] p = new int[n], sz = new int[n];
    for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; }
    int comp = n;
    for (int[] e : edges) {
        int a = find(p, e[0]), b = find(p, e[1]);
        if (a != b) {
            if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
            p[b] = a; sz[a] += sz[b]; comp--;
        }
    }
    return comp;
}
int find(int[] p, int x) { while (p[x] != x) x = p[x] = p[p[x]]; return x; }
```

### Go
```go
func countComponents(n int, edges [][]int) int {
    p, sz := make([]int, n), make([]int, n)
    for i := range n { p[i], sz[i] = i, 1 }
    find := func(x int) int {
        for p[x] != x { p[x] = p[p[x]]; x = p[x] }
        return x
    }
    comp := n
    for _, e := range edges {
        a, b := find(e[0]), find(e[1])
        if a != b {
            if sz[a] < sz[b] { a, b = b, a }
            p[b] = a; sz[a] += sz[b]; comp--
        }
    }
    return comp
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Counting roots via an extra final pass vs decrementing `components` inline during union.
- Forgetting `find(x)` path halving/compression can degrade skewed trees to O(V) per query.

### Follow-ups
- Redundant Connection asks which exact edge first triggers `find(u) == find(v)`.