問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
無向グラフのある頂点 u の次数とは、その頂点が繋がる辺の個数です。
無向グラフの全ての頂点の次数が同じ値のとき、そのグラフを正則グラフと呼びます。
無向グラフ(辺に向きがないグラフ)の隣接行列である N 次正方行列 A が与えられます。
隣接行列 A の i 行 j 列目の要素 a_{i, j} は頂点 i と頂点 j を結ぶ辺が何本あるかを表しています。
行列 A が表すグラフが正則グラフかを判定し、正則グラフならYes
、正則グラフでないならNo
を出力してください。
例えば、入力例 1 が表すのは次のようなグラフです。このグラフは全ての頂点の次数が 2 である正則グラフです。
入力例 2 が表すのは次のような行列です。このグラフは次数が 1 と 2 の頂点があるため、正則グラフではありません。
入力例 3 が表すのは次のような行列です。このグラフは全ての頂点の次数が 0 である正則グラフです。
N
a_{1,1} a_{1,2} ... a_{1,N}
a_{2,1} a_{2,2} ... a_{2,N}
...
a_{N,1} a_{N,2} ... a_{N,N}
行列 A が表すグラフが正則グラフかを判定し、正則グラフならYes
、正則グラフでないならNo
を出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて, 以下の条件をみたします
・入力はすべて整数
・与えられる隣接行列が表すグラフは自己ループを持たない
・与えられる隣接行列が表すグラフは多重辺を持つ場合がある
・1 ≦ N ≦ 100
・0 ≦ a_{i, j} ≦ 3 (1 ≦ i, j ≦ N)
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
Yes
4
0 2 0 0
2 0 0 0
0 0 0 1
0 0 1 0
No
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Yes