Skip to main content

323. Number of Connected Components in an Undirected Graph

mediumAsked at Cisco

Number of Connected Components at Cisco is the union-find warm-up. The interviewer is checking whether you reach for Union-Find with path compression and union-by-rank, OR a simpler DFS over an adjacency list. Both are valid; union-find is the answer they want when the problem later extends to dynamic edge additions.

By Sam K., Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-II onsite reports cite this as a 30-minute union-find or DFS round.
  • Blind (2025-11)— Cisco interview thread lists connected-components problems as a recurring theme.

Problem

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph.

Constraints

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no repeated edges.

Examples

Example 1

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

Explanation: Components: {0,1,2} and {3,4}.

Example 2

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

Explanation: All five nodes are connected in a chain.

Approaches

1. DFS on adjacency list

Build adjacency list. For each unvisited node, DFS its component and increment the counter.

Time
O(V + E)
Space
O(V + E)
function countComponentsDFS(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
  }
  const visited = new Array(n).fill(false);
  let count = 0;
  function dfs(node) {
    visited[node] = true;
    for (const nb of graph[node]) if (!visited[nb]) dfs(nb);
  }
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(i);
      count++;
    }
  }
  return count;
}

Tradeoff: Straightforward, linear in graph size. Use this when the graph is static and you just need the count. Recursion depth could overflow on a chain of 2000 — mention switching to BFS iteratively if pushed.

2. Union-Find with path compression + union-by-rank (optimal)

Initialize each node as its own component. For each edge, union the endpoints. Count distinct roots at the end.

Time
O((V + E) * alpha(n))
Space
O(V)
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(a, b) {
    const ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra] < this.rank[rb]) {
      this.parent[ra] = rb;
    } else if (this.rank[ra] > this.rank[rb]) {
      this.parent[rb] = ra;
    } else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
    this.components--;
    return true;
  }
}
function countComponents(n, edges) {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) uf.union(a, b);
  return uf.components;
}

Tradeoff: Nearly-linear (alpha is the inverse Ackermann function, ~4 in practice). The big advantage over DFS: you can answer 'how many components' AFTER EACH NEW EDGE in nearly-O(1) — DFS would have to re-run the full traversal. Cisco interviewers love this when the follow-up is 'now process edges as a stream.'

Cisco-specific tips

Cisco interviewers grade this on whether you can pick the right tool. State BOTH options upfront: 'DFS if the graph is static, union-find if edges are added dynamically.' If they say 'just count once', DFS is simpler. If they say 'queries arrive over time', union-find is the answer. The union-by-rank + path-compression combo is the canonical optimization — name both out loud.

Common mistakes

  • Forgetting to add the edge in BOTH directions in the adjacency list — DFS will visit only half the component.
  • Implementing union-find without path compression — each find is O(n) worst case and you lose the asymptotic improvement.
  • Forgetting that the answer is the count of DISTINCT roots after all unions — not the number of edges processed.

Follow-up questions

An interviewer at Cisco may pivot to one of these next:

  • Graph Valid Tree (LC 261) — same union-find but also check for cycles AND check exactly n-1 edges.
  • Friend Circles / Number of Provinces (LC 547) — same problem, matrix input instead of edge list.
  • Accounts Merge (LC 721) — union-find with string keys.
  • What if edges can be REMOVED? (Union-find doesn't support that; need link-cut trees or offline processing.)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Union-find or DFS — which to choose?

DFS for static graphs (one count query at the end). Union-find for dynamic graphs where edges arrive over time and you need the count after each addition. For this specific LeetCode problem (static graph, single query), both work; union-find is the more common 'production' answer Cisco interviewers expect.

Why path compression + union-by-rank?

Together they give nearly-O(1) per operation (amortized O(alpha(n)), where alpha is the inverse Ackermann function — effectively constant). Without them, find can degenerate to O(n) on a worst-case chain. Cisco interviewers expect both optimizations and will ask 'why both?' if you only mention one.

Free learning resources

Curated free links for this problem.

More Cisco coding interview questions

See all Cisco problems →