グラフの情報を、各頂点が隣接する頂点の集合の配列として持ちます。例えば C++ では頂点を int
型の整数として頂点番号によって管理するとして、std::vector<std::set<int>>
や std::vector<std::unordered_set<int>>
などのデータ構造を使用します。
この情報の持ち方では多重辺(同じ頂点対を結ぶ辺)が同一視されて一つの辺となるので、多重辺をまとめる操作である操作 A は行わなくてよくなります。よって、操作 B のみを実装すれば十分です。
以下の擬似コードの内容を実装すればこの問題に正解できます。
隣接する頂点の集合のサイズが の頂点 が存在する に隣接する頂点 を取得 が隣接する頂点の集合を空にし、 をデクリメント (実際には 自体は変更せず、別の変数を用意して使うと良い) が隣接する頂点の集合から を削除 が隣接する頂点の集合から を削除 が隣接する頂点の集合に を追加 が隣接する頂点の集合に を追加
操作 B を行うごとにグラフから辺が一つずつ減っていくので、 から始まるループ処理は最大で 回程度実行されます。