11725.백준 트리의 부모 찾기

1

import java.io.BufferedReader;

2

import java.io.BufferedWriter;

3

import java.io.InputStreamReader;

4

import java.io.OutputStreamWriter;

5

import java.util.ArrayList;

6

import java.util.StringTokenizer;

7

​

8

class Node {

9

    int no;

10

    Node parent;

11

    ArrayList<Node> adjentNodes;

12

​

13

    public Node(int no) {

14

        adjentNodes = new ArrayList<Node>();

15

        this.no = no;

16

    }

17

​

18

    public void addNode(Node item) {

19

        adjentNodes.add(item);

20

    }

21

}

22

​

23

class Main {

24

​

25

    static int[] anwser_Parent;

26

    private static StringTokenizer st;

27

    public static void main(String args[]) throws Exception {

28

​

29

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

30

        BufferedWriter bf = new BufferedWriter(new OutputStreamWriter(System.out));

31

32

        int inputLen = Integer.parseInt(br.readLine());

33

34

        anwser_Parent = new int[inputLen+1];

35

        Node[] nodes = new Node[inputLen+1];

36

        for(int i=0; i< nodes.length; i++) {

37

            nodes[i] = new Node(i);

38

        }

39

40

41

        int one,two;

42

        for (int i = 0; i < inputLen-1; i++) {

43

            st = new StringTokenizer(br.readLine());

44

            one = Integer.parseInt(st.nextToken());

45

            two = Integer.parseInt(st.nextToken());

46

47

            nodes[one].addNode(nodes[two]);

48

            nodes[two].addNode(nodes[one]);

49

        }

50

51

        nodes[1].parent = nodes[1];

52

        alertParent(nodes, nodes[1]);

53

​

54

55

        for(int i=2; i<nodes.length; i++) {

56

            bf.append(String.format("%d\n", anwser_Parent[i]));

57

        }

58

59

        bf.flush();

60

    }

61

​

62

    private static void alertParent(Node[] node, Node current) {

63

64

        for(Node child : current.adjentNodes) {

65

            if(child.parent == null) {

66

                child.parent = current;

67

                alertParent(node, child);

68

                anwser_Parent[child.no] = current.no;

69

            }

70

        }

71

72

    }

73

​

74

}

75