find connected components

🏠

Credit: Tushar

 1from collections import defaultdict
 2
 3def dfs(startNode, graph, visited, component):
 4    component.append(startNode)
 5    visited.add(startNode)
 6    
 7    for neighbor in graph[startNode]:
 8        if neighbor not in visited:
 9            dfs(neighbor, graph, visited, component)
10
11def createGraph(edges):
12    graph = defaultdict(list)
13    for startNode, endNode in edges:
14        graph[startNode].append(endNode)
15        graph[endNode].append(startNode)
16    return graph
17
18def groupProducts(productPairs):
19    
20    groups = []
21    graph = createGraph(productPairs)
22    
23    visited = set()
24    for eachStartingNode in graph:
25        if eachStartingNode not in visited:
26            component = []
27            dfs(eachStartingNode, graph, visited, component)
28            groups.append(component)
29    
30    return groups
31
32
33print(groupProducts([(1,2),(2,3),(4,5),(6,5),(7,8),(8, 1),(8,5)]))