Advertisement
viligen

break_cycles_dfs

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