演習課題「根つき木を表す配列」
根つき木について、頂点数 N と N-1 個の頂点の組(親: a_i, 子: b_i)が与えられるので、この根つき木を配列で保存し、各頂点の親を出力してください。
コードエリアには、入力値を受け取るコードと、各頂点の親を出力するコードが実装されているので、コードを書き足して完成させてください。
制約
・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
期待する出力値
parent: 3, child: 1
parent: 3, child: 2
parent: 3, child: 3
parent: 3, child: 4
parent: 1, child: 5
parent: 1, child: 6
＃04:根付き木を表す配列
このチャプターでは、根付き木を表す配列について学習します。
・頂点の数がNなら長さNの配列を作成
・配列のiには頂点iの親の頂点を保存
・1つの頂点の親の頂点は1つだけであるため、1つの1次元配列で表現可能
入力
・整数N
・N-1個の辺 (a_1, b_1), (a_2, b_2), ..., (a_{N-1}, b_{N-1})
・ただし、頂点a_iの子は頂点b_i (1 <= i <= N)
出力
・入力した根付き木に対応する配列
6
3 1
3 2
3 4
1 5
1 6
parent: 3, child: 1
parent: 3, child: 2
parent: 3, child: 3
parent: 3, child: 4
parent: 1, child: 5
parent: 1, child: 6
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 頂点の数
int[] tree = new int[N]; // 根付き木に対応する配列
// 各頂点の親を自身として初期化
for (int i = 0; i < N; i++) {
tree[i] = i;
}
// 辺の数だけループして入力
for (int i = 0; i < N-1; i++) {
int a = sc.nextInt() - 1;
int b = sc.nextInt() - 1;
// 頂点bの親を頂点aとする
tree[b] = a;
}
// 根付き木に対応する配列の内容を出力
for (int i = 0; i < N; i++) {
System.out.println("parent: %d, child: %d".formatted(tree[i] + 1, i + 1));
}
}
}