백준 11725번 - 트리의 부모 찾기(DFS)

위 문제에서 

7

1 6

6 3

3 5

4 1

2 4

4 7

을 예시로 들면

2의 부모 트리는 4

3의 부모 트리는 6

4의 부모 트리는 1

5의 부모 트리는 3

6의 부모 트리는 1

7의 부모 트리는 4

 

따라서 4 6 1 3 1 4 가 출력된다.

 

▶코드

import java.util.*;
import java.io.*;

public class Main {
    static ArrayList<Integer>[] node;
    static boolean visited[];
    static int N;
    static int result[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        node = new ArrayList[N+1];
        for(int i=1;i<=N;i++){
            node[i] = new ArrayList<Integer>();
        }
        result = new int[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            node[a].add(b);
            node[b].add(a);
        }
        dfs(1);
        for(int i=2;i<N+1;i++)
            System.out.println(result[i]);

    }
    public static void dfs(int start) {
        visited[start] = true;
        for(int val:node[start]){
            if(!visited[val]){
                result[val] = start;
                dfs(val);
            }
        }
    }
}