演習課題「木を表す隣接リスト」
木について、頂点数 N と N-1 個の辺の両端 a_i, b_i が与えられるので、この木の隣接行列を出力してください。
コードエリアには、入力値を受け取るコードと、隣接リストを出力するコードが実装されているので、コードを書き足して完成させてください。
制約
・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
期待する出力値
2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9
＃03:木を表す隣接リスト
このチャプターでは、木を表す隣接リストについて学習します。
レベルアップ問題集「木のメニュー」に収録されている「木の入力の受け取り（隣接リスト）」の問題を通して、木を隣接リストとして表現します。
入力
・整数N
・N-1個の辺 (a_1, b_1), (a_2, b_2), ..., (a_{N-1}, b_{N-1})
出力
・入力した木のグラフに対応する隣接行列
【木に対応する隣接行列】
頂点数がNならば、要素数はN^2個となって非効率
【木に対応する隣接リスト】
グラフが木ならば、リストの内側の要素数の合計は2N個となって効率が良い
2
1 2
2
1
10
1 2
2 3
3 4
4 5
6 5
7 6
8 7
9 8
10 9
2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 頂点の数
// 辺がまだ存在しない隣接リストを作成
ArrayList<ArrayList<Integer>> g = new ArrayList<>();
for (int i = 0; i < N; i++) {
g.add(new ArrayList<>());
}
// 辺の数だけループして入力
for (int i = 0; i < N-1; i++) {
int a = sc.nextInt() - 1;
int b = sc.nextInt() - 1;
// 頂点aと頂点bをつなぐ辺を隣接リストに追加
g.get(a).add(b);
g.get(b).add(a);
}
// 隣接リストの出力
for (int i = 0; i < N; i++) {
Collections.sort(g.get(i)); // 出力する頂点をソート
for (int j = 0; j < g.get(i).size(); j++) {
System.out.print(g.get(i).get(j) + 1);
if (j != g.get(i).size() - 1) {
System.out.print(" ");
}
}
System.out.println();
}
}
}