fork download
copy 
  1. import sys
  2. from collections import defaultdict
  3.  
  4.  
  5. def dfs(graph, node, visited, depth):
  6.     visited.add(node)
  7.     max_depth = depth
  8.  
  9.     for neighbor in graph[node]:
  10.         if neighbor not in visited:
  11.             max_depth = max(max_depth, dfs(graph, neighbor, visited, depth + 1))
  12.  
  13.     return max_depth
  14.  
  15. def process_graph(graph):
  16.     visited = set()
  17.     heights = []
  18.  
  19.     for node in graph:
  20.         if node not in visited:
  21.             height = dfs(graph, node, visited, 0)
  22.             heights.append(height)
  23.  
  24.     return heights
  25.  
  26. input = sys.stdin.read().splitlines()
  27. index = 0
  28. graphs = []
  29.  
  30. while index < len(input):
  31.     n = int(input[index])
  32.     index += 1
  33.     graph = defaultdict(list)
  34.  
  35.     for i in range(n):
  36.         line = list(map(int, input[index].split()))
  37.         graph[i] = line
  38.         index += 1
  39.  
  40.     graphs.append(graph)
  41.  
  42. results = []
  43. for graph in graphs:
  44.     heights = process_graph(graph)
  45.     results.append(heights)
  46.  
  47. for heights in results:
  48.     print(" ".join(map(str, heights)))
  49.  
Success #stdin #stdout 0.03s 9908KB
comments (?)
stdin
copy 
3
1
2
0 1
5
1 3
0 2 4
3
0 1 4
2 3
stdout
copy 
2
4
https://ideone.com/t7uGrT
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!