find connected components

🏠

Credit: Tushar

 1 from collections import defaultdict
 2 
 3 def 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 
11 def 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 
18 def 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 
33 print(groupProducts([(1,2),(2,3),(4,5),(6,5),(7,8),(8, 1),(8,5)]))