Number of Connected Components

Description

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

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

Approach

Introductory graph problem, solved using DFS (depth-first search). Whenever we encounter a new node, we mark it as visited and go through that entire connected component.

Using Global Variables

In Python, a global variable can be used with a Depth-First Search (DFS) algorithm, especially when the DFS function is recursive and needs to share or update a state across multiple recursive calls without passing it as an argument.

How to use:

Declare the global variable outside the function: Define the variable at the module level.

global result = [] # Example global variable

Accessing the global variable within the DFS function: If you only need to read the value of the global variable, you can access it directly within the function.

def dfs(node, graph, visited):
    global result = []
    visited.add(node)
    result.append(node) # Accessing global variable
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)

Solution

from collections import defaultdict
class Solution(object):
def countComponents(self, n, edges):
nodes = defaultdict(list)
visited = set()
visit_cnt = 0

    for edge in edges:
        nodes[edge[0]].append(edge[1])
        nodes[edge[1]].append(edge[0])
    
    def dfs(node):
        for next_node in nodes[node]:
            print(nodes[node])
            if next_node not in visited:
                visited.add(next_node)
                dfs(next_node)

    for i in range(n):
        if i not in visited:
            visited.add(i)
            visit_cnt += 1
            dfs(i)

    return visit_cnt