323. Number of Connected Components in an Undirected Graph

solve.py

from collections import deque, defaultdict

# 323. Number of Connected Components in an Undirected Graph
def solve(n, edges):

    def bfs(i, adj, visited):
        q = deque()
        q.append(i)

        while q:
            # process node
            curr = q.popleft()
            visited.add(curr)

            # add all unvisited neighbors to the queue
            for j in range(len(adj[curr])):
                if adj[curr][j] not in visited:
                    q.append(adj[curr][j])

    # build adj list, (node, neighbors)
    adj = defaultdict(list)
    for j in range(len(edges)):
        # graph is undirected, create 2 edges
        adj[edges[j][0]].append(edges[j][1])
        adj[edges[j][1]].append(edges[j][0])

    # if node has not been visited, run bfs
    # and bump up count
    visited = set()
    count = 0
    for i in range(n):
        if i not in visited:
            bfs(i, adj, visited)
            count += 1
    return count

    
n = 5
# edges = [[0, 1], [1, 2], [3, 4]]
edges = [[0, 1], [1, 2], [3, 4]]
print(solve(n, edges))