[白俊]1275号:木を探す親
6628 ワード
📌 質問する
根のない木をあげます.ツリーのルートディレクトリが1の場合、各ノードの親ノードを解くプログラムを作成します.
入力
第1行は、ノード数N(2≦N≦100000)を与える.2行目から、ツリーに接続された2点がN−1行に与えられる.
しゅつりょく
1行目からN-1行目まで、各ノードの親ノード番号が2番目のノードから順次出力されます.
入力例1
7
1 6
6 3
3 5
4 1
2 4
4 74
6
1
3
1
412
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 121
1
2
3
3
4
4
5
5
6
6import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static int N;
static ArrayList< ArrayList<Integer> > list = new ArrayList<>();
static int[] parents;
public static void base() throws IOException {
N = Integer.parseInt(br.readLine());
for(int i=0; i<=N+1; i++) {
list.add(new ArrayList<>());
}
parents = new int[N+1];
}
public static void main(String[] args) throws IOException {
base();
for(int i=1; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list.get(a).add(b);
list.get(b).add(a);
}
int start = 1;
bfs(start);
for(int i=2; i<parents.length; i++) {
System.out.println(parents[i]);
}
}
public static void bfs(int start) {
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(start);
parents[start] = 1;
while(!queue.isEmpty()) {
int parent = queue.poll();
for(int item : list.get(parent)) {
if(parents[item] == 0) {
parents[item] = parent;
queue.offer(item);
}
}
}
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static int N;
static ArrayList<Integer>[] list;
static int[] parents;
public static void base() throws IOException {
N = Integer.parseInt(br.readLine());
list = new ArrayList[N+1];
for(int i=1; i<=N; i++) {
list[i] = new ArrayList<Integer>();
}
parents = new int[N+1];
}
public static void main(String[] args) throws IOException{
base();
for(int i=0; i<N-1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
list[a].add(b);
list[b].add(a);
}
dfs(1, 0);
for(int i=2; i<=N; i++) {
System.out.println(parents[i]);
}
}
public static void dfs(int start, int parent) {
parents[start] = parent;
for(int item : list[start]) {
if(item != parent) {
dfs(item, start);
}
}
}
}BFS vs DFS
1.Breadth First Search(BFS)/幅を優先的に参照
=>まず自然に入り、隣接ノードからナビゲート
Reference
この問題について([白俊]1275号:木を探す親), 我々は、より多くの情報をここで見つけました https://velog.io/@h_seung2/백준-11275번-트리의-부모-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol