fork download
copy 
  1. import sys
  2. from collections import deque, defaultdict
  3.  
  4. def bfs(graph, start, visited):
  5.     queue = deque([(start, 0)])
  6.     visited.add(start)
  7.     max_depth = 0
  8.  
  9.     while queue:
  10.         node, depth = queue.popleft()
  11.         max_depth = max(max_depth, depth)
  12.  
  13.         for neighbor in graph[node]:
  14.             if neighbor not in visited:
  15.                 visited.add(neighbor)
  16.                 queue.append((neighbor, depth + 1))
  17.  
  18.     return max_depth
  19.  
  20. # Read the input from stdin
  21. def read_input():
  22.     input = sys.stdin.read().splitlines()
  23.     n = int(input[0])  # number of nodes
  24.     graph = defaultdict(list)
  25.  
  26.     for i in range(n):
  27.         line = list(map(int, input[i + 1].split()))
  28.         graph[i] = line  # adjacency list for each node
  29.  
  30.     return graph
  31.  
  32. # Main function
  33. def main():
  34.     graph = read_input()
  35.  
  36.     visited = set()
  37.     heights = []
  38.  
  39.     for node in graph:
  40.         if node not in visited:
  41.             height = bfs(graph, node, visited)
  42.             heights.append(height)
  43.  
  44.     # Print the heights of each tree in the BFS forest
  45.     for height in heights:
  46.     	if height>0:
  47.         	print(height, end=" ")
  48.  
  49. # Entry point
  50. main()
  51.  
Success #stdin #stdout 0.04s 9856KB
comments (?)
stdin
copy 
8
1 2 3
0
0 7
1 2
2 3
6
0 1 5
1 4
stdout
copy 
3 1
https://ideone.com/koDcTr
language:
Python 3 (python  3.9.5)
created:
7 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!