323. Number of Connected Components in an Undirected Graph

At a Glance

Topic: graphs
Pattern: Union-Find or DFS/BFS
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Apple
Frequency: Medium
LeetCode: 323 (Premium)

Problem (one-liner)

Given n nodes 0..n-1 and a list of undirected edges, return the number of connected components.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Static connectivity count
Undirected edges — Union-Find merge or DFS flood

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Adjacency + DFS — O(n+e) time, O(n+e) space.
Union-Find — O(n α(n)) — compact for edge-list input.

Optimal Solution

Go

type unionFind struct {
	parent []int
}

func newUnionFind(size int) *unionFind {
	parent := make([]int, size)
	for index := range parent {
		parent[index] = index
	}
	return &unionFind{parent: parent}
}

func (finder *unionFind) find(node int) int {
	if finder.parent[node] != node {
		finder.parent[node] = finder.find(finder.parent[node])
	}
	return finder.parent[node]
}

func (finder *unionFind) union(left int, right int) {
	rootLeft := finder.find(left)
	rootRight := finder.find(right)
	if rootLeft != rootRight {
		finder.parent[rootRight] = rootLeft
	}
}

func countComponents(nodeCount int, edges [][]int) int {
	finder := newUnionFind(nodeCount)
	for _, edge := range edges {
		finder.union(edge[0], edge[1])
	}
	roots := map[int]struct{}{}
	for node := 0; node < nodeCount; node++ {
		roots[finder.find(node)] = struct{}{}
	}
	return len(roots)
}

JavaScript

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, index) => index);
  }

  find(node) {
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]);
    }
    return this.parent[node];
  }

  union(left, right) {
    const rootLeft = this.find(left);
    const rootRight = this.find(right);
    if (rootLeft !== rootRight) {
      this.parent[rootRight] = rootLeft;
    }
  }
}

function countComponents(nodeCount, edges) {
  const finder = new UnionFind(nodeCount);
  for (const edge of edges) {
    finder.union(edge[0], edge[1]);
  }
  const roots = new Set();
  for (let node = 0; node < nodeCount; node += 1) {
    roots.add(finder.find(node));
  }
  return roots.size;
}