\(N\) 頂点 \(N\) 辺の連結なグラフ（通称 なもりグラフ）は、ちょうど一つの閉路及びその閉路上の頂点を根とする木として見ることができます。

この問題では、閉路を検出し、次に各頂点がどの閉路上の頂点を根とする木に属しているかが分かればよいです。何故ならば、同じ頂点を根としている場合単純パスは一意であり、そうでない場合閉路の通り方が \(2\) 通りあるため単純パスは一意でないからです。

様々な実装方針がありますが、ここではそのうち一例を紹介します。

step 1

次数 \(1\) の頂点及びその頂点から伸びる辺を削除することを、次数 \(1\) の頂点がなくなるまで繰り返します。この操作の後に残った頂点が、閉路上の頂点です。

step 2

閉路上の各頂点から dfs をすることで、各頂点がどの閉路上の頂点を根とする木に属しているか求めます。

実装例(c++)