fork(6) 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. 		Solution sol = new Solution();
  13. 		ArrayList<ArrayList<Integer>> B = new ArrayList<>();
  14. 		int A;
  15. 		Scanner sc = new Scanner(System.in);
  16. 		A = sc.nextInt();
  17. 		for (int i = 0; i < A - 1; i++) {
  18. 			B.add(new ArrayList());
  19. 			B.get(i).add(sc.nextInt());
  20. 			B.get(i).add(sc.nextInt());
  21. 		}
  22. 		System.out.println(sol.solve(A,B));
  23. 	}
  24. }
  25. class Solution {
  26.  
  27.     ArrayList<ArrayList<Integer>> edges;
  28.     HashMap<Integer, ArrayList<Integer>> levelMap;
  29.     int minLevel;
  30.     boolean[] visited;
  31.  
  32.     public ArrayList<Integer> solve(int A, ArrayList<ArrayList<Integer>> B) {
  33.  
  34.         edges = new ArrayList<>();
  35.         visited = new boolean[A + 1];
  36.         levelMap = new HashMap<>();
  37.         minLevel = 0;
  38.  
  39.         for (int i = 0; i < A + 1; i++) {
  40.             edges.add(new ArrayList<>());
  41.         }
  42.  
  43.         for (int i = 0; i < B.size(); i++) {
  44.             int u = B.get(i).get(0);
  45.             int v = B.get(i).get(1);
  46.             edges.get(u).add(v);
  47.             edges.get(v).add(-1 * u);
  48.         }
  49.  
  50.         dfs(1, 0);
  51.  
  52.         ArrayList<Integer> ans = levelMap.get(minLevel);
  53.         Collections.sort(ans);
  54.         return ans;
  55.     }
  56.  
  57.     void dfs (int node, int level) {
  58.         if (visited[node]) {
  59.             return;
  60.         }
  61.  
  62.         visited[node] = true;
  63.  
  64.         if (level < minLevel) {
  65.             minLevel = level;
  66.         }
  67.  
  68.         saveLevel(node, level);
  69.  
  70.         ArrayList<Integer> edgesList = edges.get(node);
  71.         for (int i = 0; i < edgesList.size(); i++) {
  72.             int v = edgesList.get(i);
  73.  
  74.             if (v > 0) {
  75.                 dfs (Math.abs(v), level + 1);
  76.             } else {
  77.                 dfs (Math.abs(v), level - 1);
  78.             }
  79.  
  80.  
  81.         }
  82.  
  83.     }
  84.  
  85.     void saveLevel (int node, int level) {
  86.         if (!levelMap.containsKey(level)) {
  87.             levelMap.put(level, new ArrayList());
  88.         }
  89.         levelMap.get(level).add(node);
  90.     }
  91. }
  92.  
Success #stdin #stdout 0.09s 35472KB
comments (?)
stdin
copy 
3
2 1
2 3
stdout
copy 
[2]
https://ideone.com/61lNrX
language:
Java (HotSpot 12)
created:
3 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!