Advertisement
MrFishPL

Zadanie z grafem - Python

Nov 27th, 2021
856
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.88 KB | None | 0 0
  1. from sys import setrecursionlimit
  2. setrecursionlimit(10001)
  3.  
  4. n = int(input())
  5.  
  6. graf = [[] for _ in range(n)]
  7. distances = [[0 for _ in range(n)] for _ in range(n)]
  8. visited = [False for _ in range(n)]
  9. maximum = 0
  10.  
  11. for _ in range(n-1):
  12.     a, b = map(int, input().split())
  13.     graf[a-1].append(b-1)
  14.     graf[b-1].append(a-1)
  15.  
  16.  
  17. def DFS(v, parent):
  18.     global graf
  19.     global distances
  20.     global visited
  21.     global maximum
  22.     global n
  23.  
  24.     if parent != -1:
  25.         for i in range(n):
  26.             if visited[i]:
  27.                 distances[i][v] = distances[i][parent] + 1
  28.                 distances[v][i] = distances[parent][i] + 1
  29.  
  30.                 if distances[v][i] > maximum:
  31.                     maximum = distances[v][i]
  32.  
  33.     visited[v] = True
  34.     for neighbor in graf[v]:
  35.         if not visited[neighbor]:
  36.             DFS(neighbor, v)
  37.  
  38. DFS(0, -1)
  39. print(maximum)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement