백준 11725번 트리의 부모 찾기

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class BaekJoon11725_P392_Q67 {
	static ArrayList<Integer> []tree;
	static int []parent;
	static Queue<Integer> qu;
	
	public static void bfs(int root) {
		qu.add(root);

		while(!qu.isEmpty()) {
			int crnt = qu.poll();
			
			for(int next : tree[crnt]) {
				if(parent[next]==0) {
					parent[next] = crnt;
					qu.add(next);
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));
		
		int nodes =Integer.parseInt(br.readLine());
		tree = new ArrayList[nodes+1];
		parent = new int[nodes+1];
		qu = new ArrayDeque<>();
		
		for(int i=0;i<tree.length;i++) {
			tree[i] = new ArrayList<>();
		}
		
		for(int i=1;i<nodes;i++) {
			StringTokenizer st =new StringTokenizer(br.readLine(), " ");
			int x=Integer.parseInt(st.nextToken());
			int y =Integer.parseInt(st.nextToken());
			tree[x].add(y);
			tree[y].add(x);
		}
		
		bfs(1);
		for(int i=2;i<=nodes;i++) {
			bw.write(parent[i]+"\n");
		}
		bw.flush();
	}

}