0 
#include<bits/stdc++.h>
 using namespace std;
  void addEdge(vector<vector<int > >&adj,int u,int v)
   {
     adj[u].push_back(v);
   }
   bool DFS(vector<vector<int > >adj,int x,vector<bool>&visited,vector<bool>&recStack,stack<int>&s)
    {
        if(recStack[x])
        {
            return true;
        }
       if(visited[x])
       {
       return false; // the node is already visited and we didn't a cycle with this node
      }
        visited[x]=true;
        recStack[x]=true;
       s.push(x);
       for(int i=0;i<adj[x].size();i++)
      {
            if(DFS(adj,adj[x][i],visited,recStack,s))
           {
             return true;
           }
      }
       recStack[x]=false;
       s.pop();
       return false;
    }
    bool graphHasCycle(vector<vector<int > >adj)
    {
          vector<bool>visited(adj.size(),false);
          vector<bool>recStack(adj.size(),false);
          stack<int>s;
         for(int i=0;i<adj.size();i++)
         {
           if(DFS(adj,i,visited,recStack,s))
            {
              while(!s.empty())
             {
            cout<<s.top()<<" ";
            s.pop();
              }
               return true;
              }
            }
           return false;
          }
         int main()
         { 
           /*int n=3,e=3;
           vector<vector<int > >adj(n,vector<int>());
           addEdge(adj,0,1);
            addEdge(adj,1,2);
            addEdge(adj,2,0);*/

            /*int n=3,e=3;
                    vector<vector<int > >adj(n,vector<int>());
                    addEdge(adj,0,1);
                   addEdge(adj,1,2);
                   addEdge(adj,0,2);*/

                /*int n=4,e=4;
               vector<vector<int > >adj(n,vector<int>());
              addEdge(adj,0,1);
              addEdge(adj,1,2);
               addEdge(adj,2,3);
               addEdge(adj,3,1);*/

               /*int n=5,e=6;
               vector<vector<int > >adj(n,vector<int>());
              addEdge(adj,0,1);
               addEdge(adj,1,2);
               addEdge(adj,0,2);
               addEdge(adj,0,3);
              addEdge(adj,3,4);
               addEdge(adj,4,0);*/

               cout<<"Adjacency list:\n";
for(int i=0;i<adj.size();i++)
{
    for(int j=0;j<adj[i].size();j++)
    {
        cout<<adj[i][j]<<" ";
    }
    cout<<endl;
}
cout<<"Cycles:\n";
if(graphHasCycle(adj))
{
    cout<<"Graph has cycle";
}
else
{
    cout<<"No cycle";
}
return 0;

}

代码来源：来自 GeeksForGeeks 的“检测有向图中的循环”。

我试图修改此代码以使用此代码打印周期，但它似乎不适用于所有情况。例如，在边为 0->1,1->2,2->3,3->1 的图中，它将循环打印为 3 2 1 0 但实际循环为 3 2 1。两个循环起源于同一个顶点。

请帮助我更正代码以正确打印周期。

在线ide代码链接： https ://ide.geeksforgeeks.org/ujCcvL77ii

4

1 回答 1

1

我认为在每次 DFS 调用之前，您需要将 recStack 重新初始化为 false，如下所示：

for(int i=0;i<adj.size();i++)
{
    vector<bool>recStack(adj.size(),false);    //for each call we need an empty recStack
    stack<int>s;                            //initialize a new stack too.
    if(DFS(adj,i,visited,recStack,s))
于 2020-05-21T09:14:16.370 回答