如何檢查無向圖中循環的存在性？

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。原因是因爲它的父j而訪問了特定頂點i，下一次當dfs爲i被調用時，頂點j將出來被訪問，因此輸出YES，這是錯誤的。

FIX

每當我們訪問一個頂點i，這已經訪問了，我們沒有立即宣佈，我們已經找到了一個循環，我們必須確保頂點i，是不是頂點的母公司，其我們稱之爲dfs，只有這樣你才能得到正確的答案。

一旦你明白了什麼是錯誤的，代碼更容易編寫。