LeetCode 323. Number of Connected Components in an Undirected Graph

Description

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

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.

Example 1:

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

Example 2:

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

Constraints:

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

Explanation

Build an adjacency list representing the relationship between vertices and edges. Then conduct depth first search to count then number of components.

Python Solution

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        
        count = 0
        
        visited = set()

        adjacency_list = []
        
        for i in range(n):
            adjacency_list.append([])
            
        for edge in edges:
            adjacency_list[edge[0]].append(edge[1])
            adjacency_list[edge[1]].append(edge[0])
            
        
        for vertice in range(n):            
            if vertice not in visited:
                self.dfs(vertice, adjacency_list, visited)
                count += 1
        
        return count
    
    
    def dfs(self, vertice, adjacency_list, visited):        
        visited.add(vertice)
        
        for adj_vertice in adjacency_list[vertice]:
            if adj_vertice not in visited:
                self.dfs(adj_vertice, adjacency_list, visited)   
       
  • Time Complexity: O(V + E). V is the number of vertices, E is the number of edges.
  • Space Complexity: O(V + E). V is the number of vertices, E is the number of edges.

Leave a Reply

Your email address will not be published.