閉路判定
(graph/cycle-detection.hpp)

• View this file on GitHub
• Last update: 2022-12-30 04:09:10+09:00
• Include: #include "graph/cycle-detection.hpp"
• Link: View error logs on GitHub Actions

Verified with

• verify/LC-CycleDetection(Directed).test.cpp

Code

vector<int> detectCycle(Graph &g){
  int n = g.size();
  const int UNUSED = 0;
  const int USING = 1;
  const int USED = 2;
  vector<int> status(n, UNUSED);
  vector<int> pre(n);
  vector<int> cycle;

  function<bool(int)> dfs = [&](int u) -> bool{
    status[u] = USING;
    for(auto &v: g[u]){
      if(status[v] == UNUSED){
        pre[v] = u;
        if(dfs(v)) return true;
      }else if(status[v] == USING){
        int cur = u;
        while(cur != v){
          cycle.push_back(pre[cur]);
          cur = pre[cur];
        }
        cycle.push_back(u);
        return true;
      }
    }
    status[u] = USED;
    return false;
  };

  for(int i = 0; i < g.size(); ++i){
    if(status[i] == UNUSED && dfs(i)){
      reverse(cycle.begin(), cycle.end());
      return cycle;
    }
  }
  return {};
};

#line 1 "graph/cycle-detection.hpp"
vector<int> detectCycle(Graph &g){
  int n = g.size();
  const int UNUSED = 0;
  const int USING = 1;
  const int USED = 2;
  vector<int> status(n, UNUSED);
  vector<int> pre(n);
  vector<int> cycle;

  function<bool(int)> dfs = [&](int u) -> bool{
    status[u] = USING;
    for(auto &v: g[u]){
      if(status[v] == UNUSED){
        pre[v] = u;
        if(dfs(v)) return true;
      }else if(status[v] == USING){
        int cur = u;
        while(cur != v){
          cycle.push_back(pre[cur]);
          cur = pre[cur];
        }
        cycle.push_back(u);
        return true;
      }
    }
    status[u] = USED;
    return false;
  };

  for(int i = 0; i < g.size(); ++i){
    if(status[i] == UNUSED && dfs(i)){
      reverse(cycle.begin(), cycle.end());
      return cycle;
    }
  }
  return {};
};

Back to top page