演習課題「木を表す隣接行列」
木について、頂点数 N と N-1 個の辺の両端 a_i, b_i が与えられるので、この木の隣接行列を出力してください。
コードエリアには、入力値を受け取るコードと、隣接行列を出力するコードが実装されているので、コードを書き足して完成させてください。
制約
・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
期待する出力値
0 1 1 1 0
1 0 0 0 0
1 0 0 0 1
1 0 0 0 0
0 0 1 0 0
＃02:木を表す隣接行列
このチャプターでは、木を表す隣接行列について学習します。
レベルアップ問題集「木のメニュー」に収録されている「木の入力の受け取り（隣接行列）」の問題を通して、木を隣接行列として表現します。
入力
・整数N
・N-1個の辺 (a_1, b_1), (a_2, b_2), ..., (a_{N-1}, b_{N-1})
出力
・入力した木のグラフに対応する隣接行列
5
1 2
1 3
1 4
5 3
0 1 1 1 0
1 0 0 0 0
1 0 0 0 1
1 0 0 0 0
0 0 1 0 0
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 頂点の数
int[][] g = new int[N][N]; // 0で初期化されたNxNの二次元配列で隣接行列を作成
// 辺の数だけループして入力
for (int i = 0; i < N-1; i++) {
int a = sc.nextInt() - 1;
int b = sc.nextInt() - 1;
// 頂点aと頂点bをつなぐ辺を隣接行列に追加
g[a][b] = 1;
g[b][a] = 1;
}
// 隣接行列の出力
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(g[i][j]);
if (j != N - 1) {
System.out.print(" ");
}
}
System.out.println();
}
}
}
木の頂点の数がNのとき、その木の辺の数はN-1になります。これは、木はすべての頂点が連結でかつ閉路が存在しないグラフであることから証明できます。