Coding

Number of Connected Components in an Undirected Graph

Asked at

Goldman Sachs

Microsoft

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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.

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

Nodes {0,1,2} form one connected component.
Nodes {3,4} form another connected component.
Total number of connected components = 2.

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

All nodes {0,1,2,3,4} are connected, forming a single connected component.
Total number of connected components = 1.

Input: n = 5, edges = [[0,1]]

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

cpp

class Solution {
public:
    int countComponents(int n, vector<vector<int>>& edges) {
        // Your code goes here
    }
};

java

class Solution {
    public int countComponents(int n, int[][] edges) {
        // Your code goes here
    }
}

python

class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        # Your code goes here

javascript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var countComponents = function(n, edges) {
    // Your code goes here
};

csharp

public class Solution
{
    public int CountComponents(int n, List<int[]> edges)
    {
        // Your code goes here
    }
}

func countComponents(n int, edges [][]int) int {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Build adjacency from edges.
02Keep a visited set or DSU parent array.
03Start a traversal at each unvisited node.
04Increment the component count per start.
05Return the count.

Reference answer

For an undirected graph, every traversal begun from an unvisited node reaches exactly one connected component. Build adjacency lists, initialize visited, and loop over all vertices. When a vertex is unvisited, increment the count and run iterative DFS or BFS, marking every reachable neighbor. Isolated vertices naturally count as components because their traversal visits only themselves. The total work is O(V+E) time and O(V+E) space. A Union-Find alternative starts with V components and decrements the count whenever an edge merges two previously separate roots; with path compression and union by rank it is effectively linear. Choose traversal when adjacency is useful; choose DSU for streaming edges or repeated connectivity queries.

Then expect these follow-ups

How would directed weak components differ?
Tests: graph definitions
When is DSU preferable?
Tests: tradeoffs

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question