Dfs implementation for undirected graph to check for cycles

general
, , , ,
1

Trying to solve SPOJ problem Is it a tree?

Based this on this tutorial

But I am always getting NO as on output. Please help where am I going wrong?

#include<iostream>
#include<cmath>
#include<vector>
#include<climits>
#include<algorithm>
#include<list>

using namespace std;

class graph
{
      public:
    long v;
    bool cyc();
    bool dfs(long v,bool visited[],long parent);

    void addedge(long v,long w);

 graph(long v);
    list<long> *adj;




};

graph::graph(long v)
{
    this->v = v;
    adj = new list<long>[v];
}

void graph::addedge(long v,long w)
{
    adj[v].push_back(w);
    adj[w].push_back(v);
}



bool graph::dfs(long v,bool visited[],long parent)
{
    visited[v] = true;
    //cout<<v<<" ";

    list<long>::iterator i;

    for(i=adj[v].begin();i!=adj[v].end();++i)
    {
        if(!visited[*i])
            {
            if (dfs(*i,visited,v))
            return true;
            }

            else if(*i!=parent)

               {
                   return true;
               }
    }

    return false;


    }









bool graph::cyc()
{
    bool *visited = new bool[v];
    long i;
    for(i=0;i<v;i++)
    {
        visited[i] =false;
    }
    for(i=0;i<v;i++)
        if(!visited[i])
           if (dfs(i,visited,-1))
            return true;
            else
                return false;


    return false;
}








int main()
{
    long m,n,v,w;
    cin>>n>>m;
    graph g(n);


    for(long i=0;i<m;i++)
    {
        cin>>v>>w;
        g.addedge(v-1,w-1);
        g.addedge(w-1,v-1);

    }

    if(m!=n-1)
    {
        cout<<"NO"<<endl;
        return 0;
    }


  if(g.cyc())
    cout<<"NO"<<endl;
  else
    cout<<"YES"<<endl;




}
2

Not only your implementation but your logic also is wrong, You are printing yes for a forest also. You just have to check two things:-

(i). All vertices are connected. (easy with one dfs/bfs just check the color of each node after traversal if any node is not black i.e its not visited, implies that graph is not connected).

(ii). Number of edges = number of vertices - 1 (A connected graph with n-1 edges can’t have a cycle the proof is very easy).

Iff a graph satisfies above two conditions then its a tree.

1 Like
3

Thank you so much. Used the above logic and now accepted :slight_smile: