fork(1) download
copy 
  1.  
  2.  
  3. 			import java.util.*;
  4. 			import java.io.*;
  5. 			class PT07Z
  6. 			{
  7.  
  8. 				static HashMap<Integer,ArrayList> map=new HashMap<Integer,ArrayList>();
  9. 				static BitSet visited=new BitSet();
  10.  
  11. 				public static void main(String args[])
  12. 				throws IOException
  13. 				{
  14. 					BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  15. 					int n=Integer.parseInt(br.readLine().trim());
  16. 					//long start=System.nanoTime();
  17. 					for(int i=0;i<(n-1);i++)
  18. 					{
  19. 						String in[]=br.readLine().trim().split(" ");
  20. 						int n1=Integer.parseInt(in[0]);
  21. 						int n2=Integer.parseInt(in[1]);
  22.  
  23. 						if(map.containsKey(n1))
  24. 						{
  25. 							ArrayList recv=map.get(n1);
  26. 							recv.add(n2);
  27. 							map.put(n1,recv);
  28. 						}
  29. 						else
  30. 						{
  31. 							ArrayList st=new ArrayList();
  32. 							st.add(n2);
  33. 							map.put(n1, st);
  34. 						}
  35. 						if(map.containsKey(n2))// ki  kore??
  36. 						{
  37. 							ArrayList recv=map.get(n2);
  38. 							recv.add(n1);
  39. 							map.put(n2, recv);
  40. 						}
  41. 						else
  42. 						{
  43. 							ArrayList st=new ArrayList();
  44. 							st.add(n1);
  45. 							map.put(n2, st);
  46. 						}
  47.  
  48. 						//
  49. 					}
  50. 					int first_end_vertex=bfs_first(1);
  51. 					//System.out.println(first_end_vertex);
  52. 					visited.clear();
  53. 					int max_length=bfs_second(first_end_vertex);
  54. 					System.out.println(max_length-1);
  55. 					//System.out.println((System.nanoTime()-start)/1000000000.0);
  56. 				}
  57.  
  58.  
  59.  
  60.  
  61.  
  62. 				static int bfs_first(int start)
  63. 				{
  64. 					int max=Integer.MIN_VALUE;
  65. 					Queue<Integer> queue=new LinkedList();
  66. 					queue.add(start);
  67. 					visited.set(start);
  68. 					int node=0,level=0,lastnode=0,no_of_children=0;
  69. 					while(!queue.isEmpty())
  70. 					{
  71. 						node=queue.remove();						
  72. 						//finding out all the unvisited child nodes adjacent to node
  73. 						int child=0;
  74. 						while((child=get_unvisited_childnode(node))!=0)
  75. 						{
  76. 							visited.set(child);
  77. 							queue.add(child);
  78. 							no_of_children++;
  79. 						}
  80. 						if((queue.size()-no_of_children==0))
  81. 						{
  82. 							level++;
  83. 							no_of_children=0;
  84. 						}
  85. 						if(level>max)
  86. 						{
  87. 							max=level;
  88. 							lastnode=node;
  89. 						}
  90. 					}
  91. 					return lastnode;
  92. 				}
  93.  
  94.  
  95. 				static int bfs_second(int start)
  96. 				{
  97. 					int max=Integer.MIN_VALUE;
  98. 					Queue<Integer> queue=new LinkedList();
  99. 					queue.add(start);
  100. 					visited.set(start);
  101. 					int node=0,level=0,lastnode=0,no_of_children=0;
  102. 					while(!queue.isEmpty())
  103. 					{
  104. 						node=queue.remove();						
  105. 						//finding out all the unvisited child nodes adjacent to node
  106. 						int child=0;
  107. 						while((child=get_unvisited_childnode(node))!=0)
  108. 						{
  109. 							visited.set(child);
  110. 							queue.add(child);
  111. 							no_of_children++;
  112. 						}
  113. 						if((queue.size()-no_of_children==0))
  114. 						{
  115. 							level++;
  116. 							no_of_children=0;
  117. 						}
  118. 						if(level>max)
  119. 						{
  120. 							max=level;
  121. 							lastnode=node;
  122. 						}
  123. 					}
  124. 					return level;
  125. 				}
  126.  
  127.  
  128. 				static int get_unvisited_childnode(int node)
  129. 				{
  130. 					ArrayList al=map.get(node);
  131. 					Iterator<Integer> list_iterator=al.iterator();
  132. 					while(list_iterator.hasNext())
  133. 					{
  134. 						int hold=list_iterator.next();
  135. 						if(!visited.get(hold))
  136. 						{
  137. 							//now mark the node as visited
  138. 							visited.set(hold);
  139. 							return hold;
  140. 						}
  141. 					}
  142. 					return 0;
  143. 				}
  144. 			}
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
3
1 2
2 3
stdout
copy 
2
https://ideone.com/vC9vsd
language:
Java (12.0.1)
created:
10 years 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!