Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Examples

Example 1:

1
2
3
4
5

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

1
2
3
4
5

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Solution

Method 1 - DFS on Graph

We can use normal DFS to find number of components. But it is good to use Union Find Data structure.

An undirected graph is represented by:

  • A number of nodes, n (labelled 0 to n-1).
  • A list of edges, each representing a connection between any two nodes.

To find the number of connected components:

  1. Think of this problem as identifying clusters of connected nodes in the graph.
  2. Use Graph Traversal Algorithms:
    • DFS (Depth First Search) or BFS (Breadth First Search) to explore each connected component fully.
  3. Maintain an array to track visited nodes. Each time you encounter an unvisited node, it’s the start of a new connected component.

Algorithm

  1. Create an adjacency list to store the graph from the input edges.
  2. Use a visited array to track whether a node has been visited.
  3. Perform a DFS or BFS from each unvisited node, marking all connected nodes as visited during traversal. For each traversal, increment the connected components count.
  4. Return the count of connected components.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int countComponents(int n, int[][] edges) {
        // Create adjacency list
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        // Visited set to track visited nodes
        boolean[] visited = new boolean[n];
        
        // DFS Helper function
        void dfs(int node) {
            visited[node] = true;
            for (int nei : graph.get(node)) {
                if (!visited[nei]) {
                    dfs(nei);
                }
            }
        }
        
        int ans = 0;
        // Iterate through all nodes
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                ans++; // A new component
                dfs(i); // Explore the entire component
            }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Create adjacency list
        graph = {i: [] for i in range(n)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Visited set to keep track of visited nodes
        visited = [False] * n
        
        def dfs(node: int) -> None:
            # Mark current node as visited
            visited[node] = True
            for nei in graph[node]:
                if not visited[nei]:
                    dfs(nei)
        
        ans = 0
        # Iterate through all nodes
        for i in range(n):
            if not visited[i]:
                ans += 1  # A new component
                dfs(i)    # Explore the entire component
        
        return ans

Complexity

  • ⏰ Time complexity: O(V + E) due to DFS
  • 🧺 Space complexity: O(V + E), Storing adjacency list uses O(V + E) space, and visited array uses O(V) space.

Method 2 - Union Find

This problem can be solved by using union-find beautifully. Initially, there are n nodes. The nodes that are involved in each edge is merged.

We can use Disjoint Set - Union by Rank Implementation

Here is the approach:

  1. Treat each node as its own component initially.
  2. Use the Union-Find/Disjoint Set data structure to group connected nodes together:
    • Union Operation: Merge two sets containing two connected nodes.
    • Find Operation: Identify the “parent” or representative of a set, enabling us to determine if two nodes belong to the same set.
    • Path Compression: Optimisation to ensure that all nodes in a set point directly to their representative, making future lookups faster.
  3. After processing all edges, count the number of distinct sets (connected components).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int countComponents(int n, int[][] edges) {
        // Initialise DSU for 'n' nodes
        var dsu = new DisjointSetUnionByRank(n);

        // Perform union operations for each edge
        for (int[] edge : edges) {
            dsu.union(edge[0], edge[1]);
        }

        // Count distinct roots (connected components)
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (dsu.find(i) == i) {
                components++;
            }
        }

        return components;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Initialise DSU for 'n' nodes
        dsu = DisjointSetUnionByRank(n)

        # Perform union operations for each edge
        for u, v in edges:
            dsu.union(u, v)

        # Count distinct roots (connected components)
        return len({dsu.find(i) for i in range(n)})

Complexity

  • ⏰ Time complexity: O(E * α(V))
    • E is the number of edges.
    • α(V) is the inverse Ackermann function, almost constant for practical purposes.
  • 🧺 Space complexity: O(V) as space is used to store the parent and rank.