data-structures - 如何检查无向图中是否存在循环？

Question

#include <bits/stdc++.h>
        using namespace std;
    int n,m;
    vector<int> adj[51];
    int visited[51];
    bool flag;
    void dfs(int i,int parent){
        vector<int>::iterator it;
        for(it = adj[i].begin();it!=adj[i].end();it++){
            if(!visited[*it]){
                visited[*it]=1;
                dfs(*it,i); // passing parent element
            }
            if(visited[*it] && (*it !=parent )){
                flag=true; return;
            }
        }
    }
    int main(){
        int a,b;
        cin>>n>>m;
        for(int i=0;i<m;i++){  // graph ready.
            cin>>a>>b;
            if(a==b){
                cout<<"YES"; return 0;
            }
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i=1;i<=n;i++){
            std::vector<int>::iterator it;
            for(it=adj[i].begin();it!=adj[i].end();it++){
                if(!visited[*it]){
                    visited[*it]=1;
                    dfs(*it,-1);
                }
            }
        }
        if(flag){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }

谁能检查我的代码并告诉我这里缺少哪个测试用例。在hackerearth 上只有60 /100。我在这里使用父变量来跟踪被认为是循环的单个边缘。

Answer 1

您得到了错误的输出，因为在adjacency list 每条边中都列出了两次。

所以说我们有一个带有3 vertices和的图表2 edges：

1------2------3

显然，不存在循环。但是您的代码也为此输入返回YES 。原因是，一旦某个特定顶点i由于其 parent 被访问j，下次调用dfsfor时i，vertexj将被访问，因此输出YES，这是错误的。

使固定

每当我们访问一个i已经访问过的 vertex 时，我们不会立即声明我们找到了一个循环，我们必须确保 vertexi不是我们调用 dfs 的 vertex 的父级，只有这样你才能得到正确的答案。

一旦您了解出了什么问题，代码就更容易编写了。