c++ - 图的一个循环中的节点数

Question

我正在尝试查找图形循环中的节点数。我正在使用递归和 DFS 来计算图中所有循环中的节点数。这是 C++ 中的计算函数。

int iscyclic(int node,bool visited[],bool rec[],vector<int>g[])
{
    if(!visited[node])
{
    visited[node] = true;
    rec[node] = true;
    vector<int>::iterator it;
    for(it=g[node].begin();it!=g[node].end();it++)
    {
        if(!visited[*it] && iscyclic(*it,visited,rec,g))
        {
            kount++;
        }
        else if(rec[*it])
            kount++;
    }
}
rec[node] = false;
return kount;
}

Visitedandrec数组默认设置为 false 并已kount全局设置为0. 应该是计算有向图的kount一个循环中的节点数。但是有些情况下答案是错误的。请帮忙。我最近开始学习图论。

Answer 1

你不应该这样做：

else if(rec[*it])
   kount++;

此外，您需要确保起始节点（您调用函数的节点）确实是循环的一部分。

第三件事 - 你kcount作为你的函数的结果返回，当你实际上应该返回true或者false基于你是否在这个分支中遇到循环的事实。