Design Gurus Logo
Solution: Number of Connected Components in an Undirected Graph
Go Back

Problem Statement

Given an undirected graph represented by 'n' nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), determine the number of connected components in the graph. A connected component is a group of nodes that are directly or indirectly linked to each other through the edges.

Examples

  1. Example 1
    • Input: n = 5, edges = [[0,1], [2,3], [3,4]]
Image
  • Expected Output: 2
  • Justification: Two components are: 0-1, and 2-3-4.
  1. Example 2
    • Input: n = 4, edges = [[0,1], [1,2], [2,3]]
Image
  • Expected Output: 1
  • Justification: All the nodes are connected in a single chain: 0-1-2-3.
  1. Example 3
    • Input: n = 3, edges = [[0,1]]
Image
  • Expected Output: 2
  • Justification: Two connected components exist: 0-1 and an isolated node 2.

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a<sub>i</sub> <= b<sub>i</sub> < n
  • a<sub>i</sub> != b<sub>i</sub>
  • There are no repeated edges.

Solution

We will use the Union-Find (also known as Disjoint Set Union, DSU) data structure to solve this problem. This approach is efficient in identifying and merging different sets:

  1. Initialization:

    • Create an array parent of size n where parent[i] = i. This array will keep track of the parent of each node. Initially, each node is its own parent.
    • Count the number of separate components. Initially, the count is n since every node is a separate component.

  2. Union Operation:

    • For each edge (u, v), find the parent of u and the parent of v.
    • If the parents are different, then u and v belong to different components. So, we merge them by assigning one's parent to the other and reduce the component count by 1.

  3. Find Operation:

    • This operation determines the parent of a node. If a node's parent is itself, return the node. Otherwise, recursively find the parent of its parent. To optimize the search in future look-ups, we can apply path compression by updating the parent of the current node to its root during the recursion.

  4. Result:

    • After processing all edges, the component count will represent the number of connected components.

Algorithm Walkthrough

Using the input n = 5 and edges = [[0,1], [2,3], [3,4]]:

  1. Initialize parent = [0, 1, 2, 3, 4] and count = 5.
  2. Process edge [0,1]:
    • Parent of 0 is 0.
    • Parent of 1 is 1.
    • They have different parents. Merge them by setting parent of 1 to 0 and reduce count to 4.
  3. Process edge [2,3]:
    • Parent of 2 is 2.
    • Parent of 3 is 3.
    • Merge them by setting parent of 3 to 2. Reduce count to 3.
  4. Process edge [3,4]:
    • Parent of 3 is 2 (from previous merge).
    • Parent of 4 is 4.
    • Merge them by setting parent of 4 to 2. Reduce count to 2.
  5. Final count is 2.

Code

Python3
Python3

Complexity Analysis

  • Time Complexity: The union operation is almost O(1) with path compression. So, for E edges, the time complexity is approximately O(E).
  • Space Complexity: O(N) due to the parent array.