 # Zadanie z grafem - Python iteracyjnie

Nov 27th, 2021
1,032
0
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 = 
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)