Advertisement
viligen

road_recunstruction_dfs

Aug 9th, 2022
575
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.85 KB | None | 0 0
  1. def dfs(node, graph, visited):
  2.     if visited[node]:
  3.         return
  4.     visited[node] = True
  5.  
  6.     for child in graph[node]:
  7.         dfs(child, graph, visited)
  8.  
  9.  
  10. buildings = int(input())
  11.  
  12. streets = int(input())
  13.  
  14. graph = [[] for _ in range(buildings)]
  15. edges = set()
  16.  
  17. for _ in range(streets):
  18.     first, second = [int(x) for x in input().split(' - ')]
  19.     graph[first].append(second)
  20.     graph[second].append(first)
  21.     edges.add((min(first, second), max(first, second)))
  22.  
  23. important = []
  24.  
  25. for first, second in edges:
  26.     graph[first].remove(second)
  27.     graph[second].remove(first)
  28.  
  29.     visited = [False] * buildings
  30.     dfs(0, graph, visited)
  31.  
  32.     if not all(visited):
  33.         important.append((first, second))
  34.     graph[first].append(second)
  35.     graph[second].append(first)
  36. print('Important streets:')
  37. for tpl in important:
  38.     print(*tpl)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement