백준 11725 - 트리의부모찾기,시뮬레이션,우선순위큐, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,dfs, priority queue

// Process
// 1. Input n, edges
// 2. Make node lists with adjacents

// 3. Make stack, and put first root node

// 4. Iterate while stack is not empty

//  4.1. Iterate adjacents

//   4.1.1. Set parent number, if this adjacent is not visited yet

// 5. Print all parent numbers from 2 to end

// 6. Finish

 

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

class FindParentTree {

    public static void main(String[] args) throws IOException {
        // 1, 2.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; ++i) {
            nodes[i] = new Node(i);
        }
        for (int i = 0; i < n-1; ++i) {
            String[] temp = br.readLine().split(" ");
            nodes[Integer.parseInt(temp[0])-1].adjacents.add(nodes[Integer.parseInt(temp[1])-1]);
            nodes[Integer.parseInt(temp[1])-1].adjacents.add(nodes[Integer.parseInt(temp[0])-1]);
        }

        // 3.
        int[] parentNumbers = new int[n];
        Stack<Node> stack = new Stack<>();
        stack.push(nodes[0]);

        // 4.
        while (stack.size() > 0) {
            Node popNode = stack.pop();
            for (int i = 0; i < popNode.adjacents.size(); ++i) {
                if (!popNode.adjacents.get(i).isVisited) {
                    stack.push(popNode.adjacents.get(i));
                    popNode.adjacents.get(i).isVisited = true;

                    parentNumbers[popNode.adjacents.get(i).value] = popNode.value;
                }
            }
        }

        // 5.
        for (int i = 1; i < parentNumbers.length; ++i) {
            System.out.println(parentNumbers[i]+1);
        }
    }
    
    static class Node {
        int value;
        boolean isVisited;
        List<Node> adjacents = new ArrayList<>();

        public Node(int value) {
            this.value = value;
            this.isVisited = false;
        }
    }
}