Number of Connected Components in an Undirected Graph - Python Solution

 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.

BFS:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = {x:[] for x in range(n)}
        for v1,v2 in edges:
            graph[v1].append(v2)
            graph[v2].append(v1)
        totalComponents = 0
        for i in range(n):
            queue = [i]
            totalComponents+= 1 if i in graph else 0
            for node in  queue:
                if node in graph:
                    queue+= graph[node]
                    del graph[node]
        return totalComponents

DFS:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = {x:[] for x in range(n)}
        for v1,v2 in edges:
            graph[v1].append(v2)
            graph[v2].append(v1)
        
        visited = set()
        def dfs(node,graph,visited):
            if node in visited:
                return
            visited.add(node)
            for nei in graph[node]:
                dfs(nei,graph,visited)
        totalComponents = 0
        for i in range(n):
            if i not in visited:
                dfs(i,graph,visited)
                totalComponents+=1
        return totalComponents

Union and Find:

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        def union(x,y):
            rx,ry = find(x),find(y)
            if rx != ry:
                parent[rx] = ry
        for x,y in edges:
            union(x,y)
        return len({find(x) for x in range(n)})