![](https://velog.velcdn.com/images/inssg/post/b81f200b-5425-4550-a4a2-f4179359f334/image.png)
- 트리는 그래프의 특수한 형태로 어떤 정점의 인접한 정점은 반드시 부모 노드 혹은 자식 노드라는 특징이 있다.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++)
tree.add(new ArrayList<>());
for (int i = 0; i < n - 1; i++) {
int n1 = sc.nextInt() - 1;
int n2 = sc.nextInt() - 1;
tree.get(n1).add(n2);
tree.get(n2).add(n1);
}
boolean[] visited = new boolean[n];
int[] parentNode = new int[n];
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
visited[0] = true;
while (!queue.isEmpty()) {
int v = queue.remove();
for (int node : tree.get(v))
if (!visited[node]) {
visited[node] = true;
queue.add(node);
parentNode[node] = v;
}
}
for (int i = 1; i < n; i++)
System.out.println(parentNode[i] + 1);
}
}