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

 

입력값으로 트리를 구성한 후 DFS 를 한다.

부모 노드를 저장할 배열을 만들어 DFS 도중에 부모 노드 정보를 저장해주면 된다.

 

 

public class Main {
    
    static int parents[];
    static ArrayList<ArrayList<Integer>> nodes;
    static boolean visited[];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        parents = new int[n+1];
        visited = new boolean[n+1];
        nodes = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<n+1; i++)
            nodes.add(new ArrayList<Integer>());
        
        for(int i=1; i<n; i++) {
            String s[] = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            nodes.get(a).add(b);
            nodes.get(b).add(a);
        }
        
        dfs(1, 0);
        for(int i=2; i<n+1; i++) System.out.println(parents[i]);
    }
    
    public static void dfs(int node, int parent) {
        visited[node] = true;
        parents[node] = parent;
        for(int item : nodes.get(node)) {
            if(item != node && !visited[item]) dfs(item, node);
        }
    }
}