無向グラフのサイクルの存在を確認する方法は？

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すべてのエッジが2回リストされているため、出力が間違っています。明らかに、何のサイクルが存在しない

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

：

は、だから我々として3 verticesと2 edgesでグラフを持っていると言います。しかし、この入力に対してもYESが返されます。理由は一度特定の頂点であるiはその親のために訪問したjdfsのiが呼び出され、頂点jが出てくるので、出力YESが間違っています。

FIX

我々はすでに訪れている頂点iを訪問するたびに、我々はすぐに我々はサイクルを発見した、我々は頂点iは、頂点の親ではないことを確認する必要がありますことを宣言していません。私たちが電話したdfsは、正しい答えを得ることができます。

何がうまくいかないのか分かったら、コードを書くのが簡単です。