fork download
copy 
  1. import sys
  2. from collections import deque, defaultdict
  3.  
  4.  
  5. def bfs(graph, start, visited):
  6.     queue = deque([(start, 0)])
  7.     visited.add(start)
  8.     max_depth = 0
  9.  
  10.     while queue:
  11.         node, depth = queue.popleft()
  12.         max_depth = max(max_depth, depth)
  13.  
  14.         for neighbor in graph[node]:
  15.             if neighbor not in visited:
  16.                 visited.add(neighbor)
  17.                 queue.append((neighbor, depth + 1))
  18.  
  19.     return max_depth
  20.  
  21.  
  22. # Read the input from stdin
  23. def read_input():
  24.     input = sys.stdin.read().splitlines()
  25.     idx = 0
  26.     graphs = []
  27.  
  28.     while idx < len(input):
  29.         n = int(input[idx])
  30.         idx += 1
  31.         graph = defaultdict(list)
  32.  
  33.         for i in range(n):
  34.             line = list(map(int, input[idx].split()))
  35.             graph[i] = line
  36.             idx += 1
  37.  
  38.         graphs.append(graph)
  39.  
  40.     return graphs
  41.  
  42.  
  43. def process_graph(graph):
  44.     visited = set()
  45.     heights = []
  46.  
  47.     for node in graph:
  48.         if node not in visited:
  49.             height = bfs(graph, node, visited)
  50.             heights.append(height)
  51.  
  52.     return heights
  53.  
  54.  
  55. input = sys.stdin.read().splitlines()
  56. index = 0
  57. graphs = []
  58.  
  59. while  index < len(input):
  60.     n = int(input[index])
  61.     index+= 1
  62.     graph = defaultdict(list)
  63.  
  64.     for i in range(n):
  65.         line = list(map(int, input[index].split()))
  66.         graph[i] = line
  67.         index += 1
  68.  
  69.     graphs.append(graph)
  70.  
  71. results = []
  72. for graph in graphs:
  73.     heights = process_graph(graph)
  74.     results.append(heights)
  75.  
  76. for heights in results:
  77.     print(" ".join(map(str, heights)))
Success #stdin #stdout 0.03s 9880KB
comments (?)
stdin
copy 
3
1
2
0 1
5
1 3
0 2 4
3
0 1 4
2 3
8
1 2 3
0
0 7
1 2
2 3
6
0 1 5
1 4
0
stdout
copy 
2
2
3 1
https://ideone.com/mM9iXQ
language:
Python 3 (python  3.9.5)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!