Finding All Cycles

個人的メモ

まず強連結成分分解を行い, 各強連結成分に分けて探索を行う. 次に各強連結成分で, ある 1 点 $s$ を含む単純サイクルをすべて列挙する. 列挙し終わったらその頂点を削除してまたある 1 点を含む単純サイクルをすべて列挙するということを繰り返す(強連結成分分解は最初の 1 回しか行わない).
始点 $s$ から DFS を行い, 現在いる頂点までのパス $P$ 上の頂点 $v$ は blocked[$v$] = true にして, 2 度たどらないようにする. そして現在いる頂点 $u$ からまた再帰的に DFS の操作を続行し, パス $P$ を含む単純サイクルをすべて列挙する. 最後に $u$ から呼び出された再帰が終了すると blocked[$u$] = false にして, return する(パス $P$ を含む単純サイクルの列挙操作を終了する)のが普通だがこれだと効率が悪くなる.
そこでこのアルゴリズムではパス $P$ を含む単純サイクルがなかった場合にのみ blocked[$u$] を true のままにして return する. これはもしパス $P$ を含む単純サイクルがなかった場合パス $P - u$ を含む単純サイクルに $u$ が含まれることはないことが鍵になっている. つまり $P - u$ を含む単純サイクルを列挙する際に $u$ はたどる必要がないので blocked[$u$] を true にしたままにする. こうすることで効率の良い探索が可能になる(オーダーの意味での改善が可能になる).
言い換えると block されている頂点というのは現在いる頂点までのパス $P$ を含む単純サイクルにこれ以降必ず含まれることのない頂点となっている. ただ効率を良くしたことで例えば $P$ を含む単純サイクルが存在し, return する前に blocked[$u$] = false にする場合, これだけでは不十分になる. $u$ が unblock されたことに伴い unblock にするべき頂点が存在するからである. 言い換えると $P$ を含む単純サイクルを探索する際にはたどる必要がないが, $P - u$ を含む単純サイクルを探索する際にはたどる(考慮する)必要のある頂点というものが存在する. これは block_stack[$u$] = ($u$ を unblock した場合に unblock にすべき頂点集合) を記録しておくことで行うことができる. この unblock の操作は再帰的に起こることに注意する.
厳密に証明しようとすると少しややこしいが, 以上の操作で数え上げられるサイクルは単純サイクルで各単純サイクルはちょうど 1 回ずつ数え上げられることがわかる. また計算量は新たに単純サイクルが見つかるまでに各頂点は高々 1 度しか unblock されないことから $\O ((V + E) (c + 1))$ time となる.