Advertisement
viligen

distances_between_nodes_bfs

Aug 9th, 2022 (edited)
630
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.25 KB | None | 0 0
  1. from collections import deque
  2.  
  3.  
  4. def find_shortest_path(graph, source, destination):
  5.     qu = deque([source])
  6.     visited = {source}
  7.     parent = {source: None}
  8.  
  9.     while qu:
  10.         node = qu.popleft()
  11.         if node == destination:
  12.             break
  13.         for child in graph[node]:
  14.             if child in visited:
  15.                 continue
  16.             visited.add(child)
  17.             qu.append(child)
  18.             parent[child] = node
  19.     return parent
  20.  
  21.  
  22. def find_size(parent, destination):
  23.     size = 0
  24.     node = destination
  25.     while node is not None:
  26.         size += 1
  27.         node = parent[node]
  28.     return size -1
  29.  
  30.  
  31. nodes = int(input())
  32. pairs = int(input())
  33.  
  34. graph = {}
  35.  
  36. for _ in range(nodes):
  37.     node_str, children_str = input().split(':')
  38.     node = int(node_str)
  39.     children = [int(x) for x in children_str.split()] if children_str else []
  40.     graph[node] = children
  41.  
  42. for _ in range(pairs):
  43.     source, destination = [int(x) for x in input().split('-')]
  44.  
  45.     parent = find_shortest_path(graph, source, destination)
  46.     if destination not in parent:
  47.         print(f'{{{source}, {destination}}} -> -1')
  48.         continue
  49.  
  50.     size = find_size(parent, destination)
  51.  
  52.     print(f'{{{source}, {destination}}} -> {size}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement