viligen

connected_components_dfs

Aug 9th, 2022
620
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.51 KB | None | 0 0
  1. def dfs(node, graph, visited, connected):
  2.     if node in visited:
  3.         return
  4.     visited.add(node)
  5.     for child in graph[node]:
  6.         dfs(child, graph, visited, connected)
  7.     connected.append(node)
  8.  
  9.  
  10. n = int(input())
  11. graph = []
  12. visited = set()
  13.  
  14.  
  15. for _ in range(n):
  16.     graph.append([int(x) for x in input().split()])
  17.  
  18. for node in range(n):
  19.     if node in visited:
  20.         continue
  21.     connected = []
  22.     dfs(node, graph, visited, connected)
  23.  
  24.     print(f'Connected component:', *connected)
Advertisement
Add Comment
Please, Sign In to add comment