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()

for i in range(n):

for edge in edges:

for vertice in range(n):
if vertice not in visited:
count += 1

return count