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)]))