BFS 흐름에 parent 리시버 Pair만 해주면 된다
DFS로 가능한 것도 참고할 것
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static ArrayList<Integer>[] TP;
static int[] parent;
static boolean[] visited;
public static void main(String[] args) {
// ISC
Scanner sc = new Scanner(System.in);
int V = sc.nextInt();
// D2F
TP = new ArrayList[V+1];
for (int i = 1; i <= V; i++) {
TP[i] = new ArrayList<>();
}
for (int i = 1; i <= V; i++) {
int s = sc.nextInt();
int e = sc.nextInt();
TP[s].add(e);
TP[e].add(s);
}
parent = new int[V+1];
visited = new boolean[V+1];
// OP
DFS(1);
// OEC
for (int i = 2; i <= V; i++) {
System.out.println(parent[i]);
}
}
static void DFS(int now) {
visited[now] = true;
for (int connected : TP[now]) {
if (!visited[connected]) {
visited[connected] = true;
DFS(connected);
}
}
}
}
'Hard deck > reindexing d1' 카테고리의 다른 글
071 : 구간 합 구하기 3 (4) | 2023.06.16 |
---|---|
068 : 리프 노드의 갯수 구하기 (0) | 2023.06.16 |
070 : 트리 순회하기 (0) | 2023.06.15 |
074 : 최소 공통 조상 구하기 1 (0) | 2023.06.15 |
056 : 최단 경로 구하기 (0) | 2023.06.15 |