使用算法设计手册在有向图中查找循环

Question

所以，我正在遵循算法设计，但从书中实现的以下算法在以下情况下失败，例如，该算法是否存在问题 -

         bool directed = true;

         bool dfs(int v, 
         vector<vector<int>>& adjList,
         vector<bool>& discovered,
         vector<bool>& processed,
         vector<int>& parent)
{     
    bool ans = false;
    discovered[v] = true;

    for(auto x : adjList[v])
    {
        if(!discovered[x])
        {
            parent[x] = v;  
            ans |= dfs(x, adjList, discovered, processed, parent);
        }
        else if((!processed[x] && parent[v]!=x) || directed)
        {
            if(parent[x]!=v)
            {
                return true;
            }
        }
    }

    processed[v] = true;
    return ans;
}

这称为使用=

 for(int i = 0; i < n; ++i)
    {
        if(!discovered[i])
        {
            dfs(i, adjList, discovered, processed, parent);
                
        }
    }

它失败了，例如=

算法设计手册中的算法是错误的吗？上面打印它有一个循环？

当它探索边缘时失败 - 2 -- > 3 此时，parent[3] = 1 因此parent[3] != 2 并且它返回 true 并表示它有一个循环。

Answer 1

你能提到你指的是书中的哪一部分吗？