閉路

閉路の検出

無向グラフ

閉路が存在するか自体はトポロジカルソートによって判別可能です。

トポロジカルソート

有向グラフ

具体的な閉路のパスを1つ取得方法としては、DFSが挙げられます。

struct Edge {
  int to;
  Edge(int _to) : to(_to) {
  }
};
using Graph = vector<vector<Edge>>;

int cycle_node = -1; // 閉路上に存在するノードのid
vb seen;             // 探索済みフラグ
vb finished;         // 探索済みで、絶対にサイクルがないノード
vi history;

void dfs(const Graph& g, int idx) {
  if (finished[idx]) {
    return;
  }

  history.push_back(idx);

  // 探索終了していないけど訪問済みなノードに到達
  if (seen[idx]) {
    // それは閉路である
    cycle_node = idx;
    return;
  }

  seen[idx] = true;

  for (const auto& e : g[idx]) {
    if (finished[e.to])
      continue;

    dfs(g, e.to);

    if (cycle_node != -1)
      return;
  }

  finished[idx] = true;
  history.pop_back();
}

// 閉路のパス
// 戻り値: 0→閉路なし 1→閉路あり
// cycle: 閉路のpath
int find_cycle(const Graph& g, vector<int>& cycle) {
  ll n = g.size();

  // init
  cycle_node = -1;
  seen.assign(n, false);
  finished.assign(n, false);
  cycle.clear();

  // 全ての頂点を確認する
  rep(i, n) {
    dfs(g, i);
    // サイクルが見つかった時点でループを抜ける
    if (cycle_node != -1) {
      break;
    }
  }

  if (cycle_node == -1) {
    return 0;
  }

  // historyの始めにあるサイクルと無関係なデータを削除
  cycle.push_back(cycle_node);
  for (auto it = history.rbegin() + 1; it != history.rend(); it++) {
    if (*it == cycle[0]) {
      break;
    }
    cycle.push_back(*it);
  }
  reverse(all(cycle));

  return 1;
}

 

関連問題