Cycle in an undirected graph using dfs

Question

Please tell me why this code fails to analyse if there is a cycle in the un-directed graph? The code is below. This is the PT07Y question on spoj. What i am doing is taking a node and doing the dfs. While performing dfs if I visit the same node then I say there is a cycle. After performing dfs from a node, I make the visited array false and perform for next node until I get a cycle or all nodes are visited.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool vis[10001];

int dfs(int n,vector <int> v[],int a)
{
    vis[n]=true;
    for(int i=0;i<v[n].size();i++)
    {
        if(v[n][i]==a)
            return 1;
        if(vis[v[n][i]]==false)
        {
            dfs(v[n][i],v,a);
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,i,a,b,cc;
    cin>>n>>m;
    vector <int> v[n+1];
    memset(vis,false,n+1);
    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
    }
    for(i=1;i<=n;i++)
    {
        if(dfs(i,v,i))
        {
            cout<<"NO"<<endl;
            return 0;
        }
        memset(vis,false,sizeof(vis));
    }
    cc=-1;
    for(i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            cc++;
            if(cc>0)
            {
                cout<<"NO"<<endl;
                return 0;
            }  
            int m= dfs(i,v,-1);
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

Answer 1

Problem 1

The graph is specified to be undirected, but the input format will only specify each edge once (for one of the directions). So when you read from the input a line like 1 2, you would have to extend the adjacency list of 1 by 2 and extend the adjacency list of 2 by 1. However, in your program you only store the first direction. Therefore your representation of the graph will be incomplete.

To fix this, extend your input processing to store both directions:

  for (i = 0; i < m; i++) {
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }

Problem 2

Your dfs method behaves incorrectly:

The dfs method returns 1 if it finds the target vertex. However, this return code is not propagated along the recursion. So when you make the recursive call dfs(v[n][i], v, a); inside your dfs method, and that call returns 1, this result is ignored by the current dfs call. If the current dfs call does not find the target vertex in the current adjacency list, it will then complete the for loop and return 0.

To fix this, you would have to make sure that if the recursive dfs call returns 1, the for loop is aborted and the 1 is also returned by the current dfs call, e.g.:

if (dfs(v[n][i], v, a, n) == 1) {
  return 1;
}

With this fix applied, another problem is revealed: When the dfs method discovers the target vertex in the list of adjacent vertices, it does not rule out the edge from where the current vertex was reached. So if you have a graph 1 <-> 2 and you start dfs at 1 with target vertex 1, you would examine the list of adjacent vertices, containing 2. Traversing the edge from 1 to 2, you would examine the list of adjacent vertices, containing 1. Your method would then report that the target vertex has been found, but this is not valid because it has only been found along the edge from where you came.

To fix this, you could track the parent vertex for each dfs call. Initially, no parent is set (i.e. -1). When you go from a to b, you would pass a as the parent. At b, you would then ignore the parent a in the adjacency list of b:

So your dfs would look e.g. like this:

int dfs(int n, vector<int> v[], int a, int parent) {
  vis[n] = true;
  for (int i = 0; i < v[n].size(); i++) {
    if (v[n][i] == parent) {
      continue;
    }
    if (v[n][i] == a)
      return 1;
    if (vis[v[n][i]] == false) {
      if (dfs(v[n][i], v, a, n) == 1) {
        return 1;
      }
    }
  }
  return 0;
}

Problem 3

The performance of your implementation is not optimal (which causes a time-out on SPOJ). You can improve this by not clearing the vis array after each cycle check in your main function. Instead, reuse the vis array and only perform the cycle check on vertices that have not been visited yet:

  for (i = 1; i <= n; i++) {
    if (vis[i] == false) {
      if (dfs(i, v, i, -1)) {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  memset(vis, false, sizeof(vis));

This is enough to get your code accepted by SPOJ.

However, you could further optimize the connectivity check in your code: Instead of clearing the vis array after the cycle check and performing another series of dfs for each vertex until a second component is discovered, you could reuse the vis array and simply check if there are any unvisited vertices after the cycle checks. This would allow you to omit the second dfs series completely.