ALDS_11_A Graphを解く話
グラフの表現の理解を問う問題である.
隣接リスト表現から隣接行列表現へ変換する処理を実装する.
隣接リスト表現(Adjacency List)
・有限グラフを表現するためのリスト
・1つのリストが1つの頂点に対応して,隣接するノードが接続
隣接行列表現(Adjacency Matrix)
・有限グラフを表現するための行列
・行列の各要素は頂点のペアが隣接しているか否かを示す.
以下のサイトで,グラフと辺をいじったり行列とリストを確認できる.
実装
入力は
頂点番号 出次数 uに隣接する頂点
の形式で与えられる.
を行番号,を列番号にする.
頂点のペアに対して1は辺あり,0は辺なしで隣接行列に代入.
gist6e33ed8e2c8bdb6f8de899f271efe4f7
感想
シンプルなのでかなり簡単な問題.