Number of Connected Components in an Undirected Graph

The problem is about finding the number of connected components in an undirected graph with n nodes and a given set of edges. A connected component is a set of vertices in a graph that are linked to each other by paths.

We can solve this problem using either Depth-First Search (DFS) or Union-Find algorithm.

Depth-First Search (DFS) Solution

  1. Create Adjacency List: First, we need to represent the graph using an adjacency list. We can create a list of sets, where each set contains the nodes connected to a particular node.

  2. DFS Function: Write a recursive DFS function that visits a node and all its connected nodes. Mark the visited nodes to avoid revisiting them.

  3. Count Components: Iterate through all nodes. If a node is not visited yet, call the DFS function and increment the count of components.

Here’s the 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

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Create the adjacency list
        graph = [set() for _ in range(n)]
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)

        # DFS function to visit all connected nodes
        def dfs(node):
            if visited[node]:
                return
            visited[node] = True
            for neighbor in graph[node]:
                dfs(neighbor)

        # Initialize visited array and component count
        visited = [False] * n
        components = 0

        # Iterate through nodes and perform DFS on unvisited nodes
        for i in range(n):
            if not visited[i]:
                dfs(i)
                components += 1

        return components

The time complexity of this solution is O(n + e), where n is the number of nodes, and e is the number of edges. The space complexity is O(n + e).

Union-Find Solution

  1. Initialize Parents: Create an array to represent the parent of each node, initially pointing to itself.

  2. Find Function: Write a function to find the root (or parent) of a node.

  3. Union Function: Write a function to connect two nodes (or sets), updating the parent accordingly.

  4. Count Components: Iterate through the edges and perform union operations for each edge. Then, iterate through the parents array and count the unique roots.

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

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Find function to find the root of a node
        def find(x):
            if x != parent[x]:
                parent[x] = find(parent[x])
            return parent[x]

        # Initialize parents pointing to themselves
        parent = [i for i in range(n)]

        # Perform union operations for each edge
        for a, b in edges:
            parent[find(a)] = find(b)

        # Count unique roots (or components)
        return len(set(find(x) for x in parent))

The time complexity of the Union-Find solution is near O(n + e), and the space complexity is O(n).

 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
38
39
40
41
42
43
44
45
46
47
48
49
50

class UnionFind:
    def __init__(self, n, edges):
        self.numComponents = n
        self.parentList = [i for i in range(n)]
        # Hold the size of the component
        self.size = [1] * n

    # Path compression
    def getParent(self, node):
        currParent = node

        # Same as what our DFS solution did
        while currParent != self.parentList[currParent]:
            currParent = self.parentList[currParent]

        # path compression
        while node != currParent:
            nextParent = self.parentList[node]
            self.parentList[node] = currParent
            node = nextParent

        return currParent
    def addEdge(self, u, v):
        parentU = self.getParent(u)
        parentV = self.getParent(v)

        isConnected = parentU == parentV

        if isConnected:
            # You have a cycle!
            return

        # Naiively setting parentU to V
        if self.size[parentU] < self.size[parentV]:
            self.parentList[parentU] = parentV
            self.size[parentV] += self.size[parentU]
        else:
            self.parentList[parentV] = parentU
            self.size[parentU] += self.size[parentV]

        self.numComponents -= 1
        # Check if already connected
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n, edges)

        for u, v in edges:
            uf.addEdge(u, v)

        return uf.numComponents

Fill out the following sections:

Define the Interface Input: n (number of vertices), edges (undirected edges connecting vertices) Output: integer

Identify the Invariants

  • n, edges

Identify the constraints

  • Visit a node only once

Search the Problem Space

  • Connected Components => Union Find

Classify the Problem Graph Traversal Union Find (datastructure)

Analyze the Examples _/

Solve the Problem by Hand

Describe the Pattern

Brute Force Approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

[0,1,2,3,4]

[t,t,t,f,f] visited

count = 1 start traversing from 0 [0,1,2,3,4]

count = 2 start traversing from 3

return count

Number of dfs calls we made is equal to the number of components counter = 0 Every time before we do

 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
38

# [[0, 1], [1, 2], [3, 4]]
#   0        1       2
def adjacency_list(n, edges)
    list = (0...n).map {|node| [node, []]}.to_h
    edges.each do |edge|
        list[edge[0]] << edge[1]
        list[edge[1]] << edge[0]
    end
    list
end

def dfs(list, current_node, visited)
   visited[current_node] = true
   
   for neighbor in list[current_node]
       if !visited[neighbor]
          dfs(list, neighbor, visited) 
       end
   end
end

# @param {Integer} n
# @param {Integer[][]} edges
# @return {Integer}
def count_components(n, edges)
    count = 0
    visited = [false] * n
    list = adjacency_list(n, edges)

    for current_node in (0..n-1)
       if !visited[current_node] 
          count += 1
          dfs(list, current_node, visited)
       end
    end

    return count
end

title: Number of Connected Components in an Undirected Graph excerpt: Given n nodes labeled from 0 to n - 1 and a list of undirected edges, find the number of connected components in an undirected graph. tags: graph-traversal

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.

Example 1:

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

 0          3
 |          |
 1 --- 2    4

Output: 2

Example 2:

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

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

Output: 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.

Thought Process

Define the Interface

Input: n (number of vertices), edges (undirected edges connecting vertices) Output: integer

Identify the Invariants

  • n, edges

Identify the Constraints

  • Visit a node only once

Search the Problem Space

  • Connected Components => Union Find

Classify the Problem Graph Traversal Union Find (data structure)

Analyze the Examples Positive and negative cases.

Time and Space Complexity

Time: O(V+E) Space: O(V+E)

Solution Outline

[0,1,2,3,4]

[t,t,t,f,f] visited

count = 1 start traversing from 0 [0,1,2,3,4]

count = 2 start traversing from 3

return count

Number of dfs calls we made is equal to the number of components counter = 0 Every time before we do the traversal we increment the counter

[[0, 1], [1, 2], [3, 4]] 0 1 2

 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
38

def adjacency_list(n, edges)
  list = (0...n).map {|node| [node, []]}.to_h
  
  edges.each do |edge|
    list[edge[0]] << edge[1]
    list[edge[1]] << edge[0]
  end
  
  list
end

def dfs(list, current_node, visited)
  visited[current_node] = true
   
  for neighbor in list[current_node]
    if !visited[neighbor]
      dfs(list, neighbor, visited) 
    end
  end
end

# @param {Integer} n
# @param {Integer[][]} edges
# @return {Integer}
def count_components(n, edges)
  count = 0
  visited = [false] * n
  list = adjacency_list(n, edges)
    
  for current_node in (0..n-1)
    if !visited[current_node] 
      count += 1
      dfs(list, current_node, visited)
    end
  end

  return count
end