MrFishPL

Zadanie z grafem - Python iteracyjnie

Nov 27th, 2021
907
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. n = int(input())
  2.  
  3. graf = [[] for _ in range(n)]
  4. distances = [[0 for _ in range(n)] for _ in range(n)]
  5. visited = [False for _ in range(n)]
  6. maximum = 0
  7. parents = [-1 for _ in range(n)]
  8.  
  9. for _ in range(n-1):
  10.     a, b = map(int, input().split())
  11.     graf[a-1].append(b-1)
  12.     graf[b-1].append(a-1)
  13.  
  14.  
  15. S = [0]
  16.  
  17. # DFS iteracyjnie
  18. while S:
  19.     v = S.pop()
  20.     parent = parents[v]
  21.  
  22.     if parent != -1:
  23.         for i in range(n):
  24.             if visited[i]:
  25.                 distances[i][v] = distances[i][parent] + 1
  26.                 distances[v][i] = distances[parent][i] + 1
  27.  
  28.                 if distances[v][i] > maximum:
  29.                     maximum = distances[v][i]
  30.  
  31.     visited[v] = True
  32.     for neighbor in graf[v]:
  33.         if not visited[neighbor]:
  34.             S.append(neighbor)
  35.             parents[neighbor] = v
  36.  
  37.  
  38. print(maximum)
RAW Paste Data