Advertisement
Kamend1

Untitled

Jul 18th, 2023
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.20 KB | None | 0 0
  1. def dfs(node, destination, graph, visited):
  2. if node in visited:
  3. return
  4.  
  5. visited.add(node)
  6.  
  7. if node == destination:
  8. return
  9.  
  10. for child in graph[node]:
  11. dfs(child, destination, graph, visited)
  12.  
  13.  
  14. def path_exists(source, destination, graph):
  15. visited = set()
  16.  
  17. dfs(source, destination, graph, visited)
  18.  
  19. return destination in visited
  20.  
  21.  
  22. nodes = int(input())
  23. graph = {}
  24. edges = []
  25. for _ in range(nodes):
  26. node, children_str = input().split('->')
  27. children = children_str.split()
  28. graph[node] = children
  29. for child in children:
  30. edges.append((node, child))
  31.  
  32. removed_edges = []
  33. for source, destination in sorted(edges, key=lambda x: (x[0], x[1])):
  34. if source not in graph[destination] or destination not in graph[source]:
  35. continue
  36. graph[source].remove(destination)
  37. graph[destination].remove(source)
  38.  
  39. if path_exists(source, destination, graph):
  40. removed_edges.append((source, destination))
  41. else:
  42. graph[source].append(destination)
  43. graph[destination].append(source)
  44.  
  45. print(f'Edges to remove: {len(removed_edges)}')
  46. for node, child in removed_edges:
  47. print(f"{node} - {child}")
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement