[백준 11725] 트리의 부모 찾기(Java)

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        LinkedList<Integer>[] graph = new LinkedList[n + 1];
        boolean[] visited = new boolean[n+1];
        parent = new int[n+1];
        for(int i = 0; i <= n;i++)
            graph[i] = new LinkedList<Integer>();

        for(int i = 0; i < n - 1; i++){
            String[] s = br.readLine().split(" ");
            int v1 = Integer.parseInt(s[0]);
            int v2 = Integer.parseInt(s[1]);
            graph[v1].add(v2);
            graph[v2].add(v1);
        }
        bfs(1, graph, visited);
        for(int i = 2; i <= n; i++)
            System.out.println(parent[i]);

    }
    public static void bfs(int start, LinkedList<Integer>[] graph, boolean[] visited){
        Queue<Integer> queue = new LinkedList<Integer>();
        visited[start] = true;
        queue.add(start);

        while(queue.size() > 0){
            Integer current = queue.poll();

            for(int next : graph[current]){
                if(visited[next] == false){
                    parent[next] = current;
                    visited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}