グラフの情報を、各頂点が隣接する頂点の集合の配列として持ちます。例えば C++ では頂点を int 型の整数として頂点番号によって管理するとして、std::vector<std::set<int>>std::vector<std::unordered_set<int>> などのデータ構造を使用します。

この情報の持ち方では多重辺(同じ頂点対を結ぶ辺)が同一視されて一つの辺となるので、多重辺をまとめる操作である操作 A は行わなくてよくなります。よって、操作 B のみを実装すれば十分です。

以下の擬似コードの内容を実装すればこの問題に正解できます。

while True:\texttt{while True:}\\ if\hspace{2em} \texttt{if} \hspace{0.25em} 隣接する頂点の集合のサイズが 22 の頂点 ii が存在する:\texttt{:}\\ i\hspace{4em} i に隣接する頂点 j,kj, k を取得\\[2ex] i\hspace{4em} i が隣接する頂点の集合を空にし、NN をデクリメント (実際には NN 自体は変更せず、別の変数を用意して使うと良い)\\[2ex] j\hspace{4em} j が隣接する頂点の集合から ii を削除\\ k\hspace{4em} k が隣接する頂点の集合から ii を削除\\[2ex] j\hspace{4em} j が隣接する頂点の集合に kk を追加\\ k\hspace{4em} k が隣接する頂点の集合に jj を追加\\[2ex] else:\hspace{2em} \texttt{else:}\\ break\hspace{4em} \texttt{break}\\[2ex] ifN=2:\texttt{if} \hspace{0.5em} N = 2\texttt{:}\\ print("Yes")\hspace{2em} \texttt{print("Yes")}\\ else:\texttt{else:}\\ print("No")\hspace{2em} \texttt{print("No")}

操作 B を行うごとにグラフから辺が一つずつ減っていくので、while True:\texttt{while True:} から始まるループ処理は最大で MM 回程度実行されます。

実装例 (C++)

実装例 (Python 3)