グラフから頂点を削除する
無向グラフが与えられており、頂点数が
v、辺の数が e であるとします。各頂点の「重要度」を求めるためには、その頂点に接続している全ての辺を取り除いてから、その状態の隣接行列を出力してください。なお、ある頂点の重要度を求めるときに削除した辺は、他の頂点の重要度を求める処理には影響しません。入力
最初の行に、整数
v (1 ≤ v ≤ 50) と e (1 ≤ e ≤ 200) が与えられます。続く
e 行には、頂点 v1 と頂点 v2 (1 ≤ v1, v2 ≤ v) が互いに接続していることを示すペア v1 v2 が与えられます。出力
プログラムは、
v 個の隣接行列を改行で区切って出力します。それぞれの隣接行列は対応する頂点に接続されている辺を削除したあとでのグラフのつながりを表します。出力する隣接行列は頂点番号の昇順で表示してください。例
入力 | 出力 |
3 3
1 2
2 3
3 1 | 0 0 0
0 0 1
0 1 0
0 0 1
0 0 0
1 0 0
0 1 0
1 0 0
0 0 0 |
解説
# 初期の隣接行列
0 1 1
1 0 1
1 1 0
# 頂点 1 を削除した場合
0 0 0
0 0 1
0 1 0
# 頂点 2 を削除した場合
0 0 1
0 0 0
1 0 0
# 頂点 3 を削除した場合
0 1 0
1 0 0
0 0 0Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB