11725 나무의 부모 찾기
주어는 뿌리가 없는 나무입니다.
이때 트리의 루트를 1로 설정하고 각 노드의 부모를 찾는 프로그램을 작성한다.
www.acmicpc.net
문제
주어는 뿌리가 없는 나무입니다.
이때 트리의 루트를 1로 설정하고 각 노드의 부모를 찾는 프로그램을 작성한다.
기입
노드 수 N(2 ≤ N ≤ 100,000)은 첫 번째 줄에 제공됩니다.
트리에 연결된 두 개의 노드는 두 번째 줄부터 N-1 줄에 주어집니다.
누르다
첫 번째 라인부터 N-1 라인에는 각 노드의 부모 노드 번호가 노드 2부터 순서대로 출력됩니다.
설명
- num1과 num2는 연결되어 있으므로 tree(num1)에 num2를, tree(num2)에 num1을 넣어야 합니다.
- 결과적으로 Tree(1) = {6, 4} / Tree(2) = {4} / Tree(3) = {6, 5} / Tree(4) = {1, 2, 7} / Tree( 5 ) ) = {3} / 트리(6) = {1, 3} / 트리(7) = {4}.
- dfs(깊은 우선 검색)를 구현하려면 스택을 방문했는지 확인하기 위해 방문 배열을 만들고 출력에 대한 부모 노드를 포함하는 부모 배열을 만듭니다.
- 먼저 스택에 1을 올려 루트 노드를 1로 표시하고 Visited를 true로 변경합니다.
- tree(1)은 6과 4를 포함하므로 parent(6) = 1이고 parent(4) = 1입니다.
- tree(4)의 경우 1, 2, 7이 포함되지만,visited(1) = true이므로 parent(1) = 4는 발생하지 않는다.
- 스택에서 5가 제거될 때까지 반복합니다.
- 먼저 스택에 1을 올려 루트 노드를 1로 표시하고 Visited를 true로 변경합니다.
- 노드 2에서 인쇄하도록 지시했으므로 2에서 for 문을 시작합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String() args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine()); // 노드의 개수
// 인접 리스트 구성
ArrayList<Integer>() tree = new ArrayList(n + 1);
for (int i = 1; i <= n; i++) {
tree(i) = new ArrayList<>();
}
// tree 에 값 넣기
for (int i = 0; i < n - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
tree(num1).add(num2);
tree(num2).add(num1);
}
// dfs
int() parent = new int(n + 1);
boolean() visited = new boolean(n + 1);
Stack<Integer> stack = new Stack<>();
stack.push(1);
visited(1) = true;
while (!
stack.isEmpty()) {
int cur = stack.pop();
for (int child : tree(cur)) {
if (!
visited(child)) {
stack.push(child);
parent(child) = cur;
visited(child) = true;
}
}
}
for (int i = 2; i <= n; i++) {
System.out.println(parent(i));
}
}
}