ALDS_11_A Graphを解く話 - tooshitaka’s diary

グラフの表現の理解を問う問題である．

隣接リスト表現から隣接行列表現へ変換する処理を実装する．

・有限グラフを表現するためのリスト
・1つのリストが1つの頂点に対応して，隣接するノードが接続

・有限グラフを表現するための行列
・行列の各要素は頂点のペアが隣接しているか否かを示す．

以下のサイトで，グラフと辺をいじったり行列とリストを確認できる．

入力は
　頂点番号 $u$ 　出次数 $k$ 　uに隣接する頂点 $v_1, v_2, ..., v_k$
の形式で与えられる．

$u = 1\ to\ n$ を行番号， $j = 1\ to\ k$ を列番号にする．
頂点のペアに対して1は辺あり，0は辺なしで隣接行列 $m_{uj}$ に代入．

シンプルなのでかなり簡単な問題．