[BOJ] 11725. ツリーの親を検索
https://www.acmicpc.net/problem/11725
質問する
nの最大値は100000であるため、隣接行列を採用すると100000*100000となる.実行中にエラーが発生しました.
隣接リストで表現しましょう. までうまく解決できなかったツリー巡り問題DFSもお馴染みになってきたので不思議に記録しましたが、ふふ
質問する
根のない木をあげます.ツリーのルートディレクトリが1の場合、各ノードの親ノードを解くプログラムを作成します.
入力
第1行は、ノード数N(2≦N≦100000)を与える.2行目から、ツリーに接続された2つの頂点がN−1行に与えられる.
しゅつりょく
1行目からN-1行目まで、各ノードの親ノード番号が2番目のノードから順次出力されます.
に答える import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer> [] graph;
static int[] parent;
static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
graph = new ArrayList[n + 1];
visit = new boolean[n + 1];
parent = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
graph[i] = new ArrayList<>();
}
StringTokenizer st;
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int to = Integer.parseInt(st.nextToken());
int from = Integer.parseInt(st.nextToken());
graph[to].add(from);
graph[from].add(to);
}
dfs(1);
for (int i = 2; i <= n; i++)
System.out.println(parent[i]);
}
static void dfs(int start) {
for (int child : graph[start]) {
if (visit[child]) continue;
parent[child] = start;
visit[child] = true;
dfs(child);
}
}
}
第1行は、ノード数N(2≦N≦100000)を与える.2行目から、ツリーに接続された2つの頂点がN−1行に与えられる.
しゅつりょく
1行目からN-1行目まで、各ノードの親ノード番号が2番目のノードから順次出力されます.
に答える import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer> [] graph;
static int[] parent;
static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
graph = new ArrayList[n + 1];
visit = new boolean[n + 1];
parent = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
graph[i] = new ArrayList<>();
}
StringTokenizer st;
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int to = Integer.parseInt(st.nextToken());
int from = Integer.parseInt(st.nextToken());
graph[to].add(from);
graph[from].add(to);
}
dfs(1);
for (int i = 2; i <= n; i++)
System.out.println(parent[i]);
}
static void dfs(int start) {
for (int child : graph[start]) {
if (visit[child]) continue;
parent[child] = start;
visit[child] = true;
dfs(child);
}
}
}
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer> [] graph;
static int[] parent;
static boolean[] visit;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
graph = new ArrayList[n + 1];
visit = new boolean[n + 1];
parent = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
graph[i] = new ArrayList<>();
}
StringTokenizer st;
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int to = Integer.parseInt(st.nextToken());
int from = Integer.parseInt(st.nextToken());
graph[to].add(from);
graph[from].add(to);
}
dfs(1);
for (int i = 2; i <= n; i++)
System.out.println(parent[i]);
}
static void dfs(int start) {
for (int child : graph[start]) {
if (visit[child]) continue;
parent[child] = start;
visit[child] = true;
dfs(child);
}
}
}
隣接リストで表現しましょう.
Reference
この問題について([BOJ] 11725. ツリーの親を検索), 我々は、より多くの情報をここで見つけました https://velog.io/@yoon_0/BOJ-11725.-트리의-부모-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol