在有向图中求循环

Question

我正在解决一个问题，以确定图是否包含循环。我使用着色方法解决了它(在已访问的数组中，我将标记0，如果它从未访问过，则标记1，如果已访问顶点，则标记2(为此，我编写了代码：

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[20005];
int vis[20005];
int chk = 0;
void dfs(int u){
if(vis[u]==1) {
chk = 1;
return;
}
if(vis[u]==2) return;
vis[u] = 1;
for(auto v:adj[u]) dfs(v);
vis[u] = 2;
} 
int main(){
int N, M; cin>>N>>M;
for(int i = 0; i<M; i++){
int p, q; cin>>p>>q;
adj[p].push_back(q);
}
for(int i = 1; i<=N; i++){
if(vis[i]==1) break;
if(!vis[i]) dfs(i);
}   
cout<<(chk?"Yesn":"Non");
}

现在，我在想，如果有一种方法可以写出已经检测到的周期。我知道大多数人会说DFS和回溯，这是非常直观的。但我想知道如何实现它。

Answer 1

par[v]-v的父节点，pr-以前访问过的节点：

void dfs(int u, int pr = -1){
if(vis[u]==1) {
vector<int> cycle();
int cur = pr;
while(cur != u) {
cycle.push_back(cur);
cur = par[cur]
}
cycle.push_back(u);
chk = 1;
return;
}
if(vis[u]==2) return;
vis[u] = 1;
par[u] = pr;
for(auto v:adj[u]) dfs(v, u);
vis[u] = 2;
}