fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		 Scanner sc = new Scanner(System.in);
  13.  
  14.         int n = sc.nextInt(); // number of nodes
  15.         List<Integer>[] child = new List[n + 1];
  16.         for (int i = 0; i <= n; i++) {
  17.             child[i] = new ArrayList<>();
  18.         }
  19.  
  20.         // Read n-1 edges
  21.         for (int i = 0; i < n - 1; i++) {
  22.             int u = sc.nextInt();
  23.             int v = sc.nextInt();
  24.             child[u].add(v);
  25.             child[v].add(u);
  26.         }
  27.  
  28.         int[] used = new int[n + 1];
  29.         int[] parent = new int[n + 1];
  30.         int[] height = new int[n + 1];
  31.  
  32.         dfs(child, 0, used, parent, height);
  33.  
  34.         System.out.println("Height of tree rooted at node 0: " + height[0]);
  35.     }
  36.  
  37.     public static void dfs(List<Integer>[] child, int node, int[] used, int[] parent, int[] height) {
  38.         used[node] = 1;
  39.  
  40.         for (int v : child[node]) {
  41.             if (used[v] == 0) {
  42.                 parent[v] = node;
  43.                 dfs(child, v, used, parent, height);
  44.             }
  45.         }
  46.  
  47.         int h = 0;
  48.         for (int v : child[node]) {
  49.             if (v == parent[node]) continue;
  50.             h = Math.max(h, height[v]);
  51.         }
  52.  
  53.         height[node] = 1 + h;
  54. 	}
  55. }
Success #stdin #stdout 0.14s 58908KB
comments (?)
stdin
copy 
5
0 1
0 2
1 3
1 4
stdout
copy 
Height of tree rooted at node 0: 3
https://ideone.com/O70lQ6
language:
Java (12.0.1)
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!