cycle_detection_directed

関数 · 有向グラフの閉路検出（閉路を構成する辺 ID 列を返す）

template <graph_type G>
std::vector<int> cycle_detection_directed(const G &g);

概要

有向グラフの閉路検出（閉路を構成する辺 ID 列を返す）

テンプレートパラメータ

名前	説明
`G`	グラフ型（`list_graph<T>` / `csr_graph<T>` のいずれでも可）

戻り値

閉路を構成する辺 ID の列（入力順で連結する）。閉路が無ければ空。

計算量

$O(V+E)$

備考

各辺 ID は list_graph::add_edge の追加順（= 入力順）。多重辺・自己ループに対応。

関連項目

cycle_detection_undirected — 無向グラフの閉路検出（閉路を構成する頂点列と辺 ID 列を返す）
has_cycle — 閉路検出