c++ - 使用 dfs 和高度数组在无向图中进行循环检测

Question

我的工作是在下面的程序中完成 isCyclic() 函数。我可以使用已访问数组并将父级传递给 dfs() 函数来处理这项工作，但我正在尝试另一种解决方案，因此我使用高度数组来跟踪 DFS 树中节点的距离，以确定父级和循环。这个高度数组初始为零。如果两个节点的距离正好是 1，那么这两个节点就是父子节点。但我不明白为什么我的解决方案不起作用。有人能告诉我为什么这段代码的输出不正确吗？谢谢你的帮助。

节点的图形和高度值示例：

   /*
    .1
   / \
  .2  .2
     / \
    .3  .3
 */
#include<bits/stdc++.h>
using namespace std;
class Graph
{
    int V;
    list<int> *adj;
public :
    Graph(int V);
    void addEdge(int v,int w);
    bool isCyclic();
};
vector<int> g[100001];
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
void Graph::addEdge(int v,int w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int _size,N;
        cin>>_size>>N;
        Graph *g = new Graph(_size);
        for(int i=0;i<N;i++)
        {
            int u,v;
            cin>>u>>v;
            g->addEdge(u,v);
        }
        cout<<g->isCyclic()<<endl;
    }
}


/*Please note that it's Function problem i.e.
you need to write your solution in the form of Function(s) only.
Driver Code to call/invoke your function is mentioned above.*/

/*The structure of the class is as follows 
which contains an integer V denoting the no 
of vertices and a list of adjacency vertices.
class Graph
{
    int V;
    list<int> *adj;
public :
    Graph(int V);
    void addEdge(int v,int w);
    bool isCyclic();
};*/
/*You are required to complete this method*/

bool dfs(int v, int hi, list<int> *adj, int *h) {
    h[v] = hi;

    list<int>::iterator it;
    for(it = adj[v].begin(); it != adj[v].end(); it++) {
        int u = *it;

        //cycle detect
        if (h[u]>0 && hi - h[u] > 1)
            return true;

        if (h[u]==0 && dfs(u, hi+1, adj, h))
            return true;
    }

    return false;
}

/*You are required to complete this method*/
bool Graph :: isCyclic()
{
//Your code here
    int h[V];
    for(int i = 0; i < V; i++) h[i] = 0;

    for(int i = 0; i< V; i++) 
        if ( h[i] == 0 && dfs(i, 1, adj, h) ) return true;
    return false;
}

使我的答案不正确的输入：

输入：85 59 0 34 32 54 6 16 45 44 82 52 57 15 20 60 52 44 75 77 48 18 53 75 14 40 39 46 24 26 32 0 39 74 34 29 43 41 45 45 0 75 3 15 34 63 16 39 81 69 29 52 67 26 14 6 52 3 48 49 77 83 78 78 81 38 38 38 38 8 53 53 40 84 77 31 63 9 70 16 78 57 69 60 4 83 83 6 23 72 70 23 2 24 61 40 74 71 50 29 28 42 60 48 51 2 64 2 59 48 19 57

它的正确输出是：1

你的代码的输出是：0

标签： c++graphdepth-first-search