무향 그래프에서 사이클의 존재를 확인하는 방법은 무엇입니까?

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을 얻었습니다. 루프로 간주되는 단일 에지를 추적하기 위해 여기서 parent 변수를 사용하고 있습니다.

Answer 1

adjacency list모든 가장자리가 두 번 나열되어 있기 때문에 잘못된 출력이 나옵니다.

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

분명히, 어떤주기가 없습니다 :

그래서 우리가 3 vertices 및 2 edges와 그래프를 말한다. 그러나이 입력에 대해서도 YES을 리턴합니다. 이유는 특정 정점입니다. i은 부모 j 때문에 방문합니다. dfs이 i 인 경우 다음 번에 정점 j이 방문 할 예정이므로 예을 출력했는데 잘못되었습니다.

FIX 우리는 이미 방문 정점 i를 방문 할 때마다

, 우리는 즉시 정점 i는, 그 정점의 부모가 아니라는 것을 우리는 확인해야합니다, 우리는 사이클을 발견했다고 선언하지 우리가 전화 한 dfs는 그때 당신이 옳은 대답을 얻을 것입니다.

무엇이 잘못되었는지 이해하면 코드를 작성하기가 더 쉽습니다.