DFS - Checking Cycles

Question

The objective is to find whether a undirected, unweighted graph is a tree, i.e. check whether it contains a back edge. I'm using a modified form of White-Gray-Black DFS algorithm(which is given in Cormen and on the notes mentioned here: http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part1.pdf )

But somehow, it doesn't work. It worked once, but it resulted in a Run Time Error at SPOJ (http://www.spoj.com/problems/PT07Y/).

Update: I'm now getting a WRONG answer for this problem. The code works for the sample test cases though.

Test case where it fails:

#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <vector>
#include <cstdlib>
using namespace std;

bool  M[10001][10001] = { 0 } ;
int color[10001] = { 0  };
long long int n;
bool answer=false;
void condition()
{
    cout<<"NO"<<endl;
    exit(0);
}
void condition2()
{
    cout<<"YES"<<endl;
    exit(0);
}

void dfs(int u, int p)
{
    color[u] = 1;
    for(int v=0; v < n; v++)
        {
            if(M[u][v] && v != p)
                {
                    if (color[v] == 0)
                        dfs(v, u);
                    else if (color[v]==1)
                    {
                         condition(); /* It has a backedge so it is not a tree, so print No */
                    }
                }
        }

    condition2(); /* It does not have backedge so it is not a tree so print YES */


}

int main()
{


long Z;
cin>>n>>Z;


// for(int i=0; i<n; i++) /* **Removed THIS nested loop to reduce runtime, successfully eliminated TLE** */
//     for(int j=0; j<n;j++)
//        M[i][j]=0;

for(int i=0; i < Z; i++)
{
    long temp1, temp2;
    cin>>temp1;
    cin>>temp2;
    temp1--;
    temp2--;

    M[temp1][temp2]=1;
    M[temp2][temp1]=1;

}


if(Z==n-1)
    dfs(0, -1);
else cout<<"NO"<<endl;

return 0;
}

Two things. The array color should probably have 20001 elements. And you use n before it has a value. — Bill Lynch
Additionally, it is very helpful if you name your variables with something longer than u, p and v. — Bill Lynch
@sharth: I've updated the array color[20001] but however as you can see, n is assigned a value before function calls. — user3125772
Please look at the first line of your main() function where you use n in the loop condition. And unless I'm mistaken, color is still an array of 128 bools. — Bill Lynch
Since the graph is undirected, shouldn't you create 2 edges for each line of the input?: M[temp1][temp2]=1; and M[temp2][temp1]=1;? — Bill Lynch

Pradhan Pradhan · Accepted Answer · 2014-06-30T04:14:53

A graph is a tree if it is connected and E = V-1, where E and V are the number of edges and nodes respectively. So, you should be able to solve it in O(V) time as long you check that E==V-1 before launching the DFS.

Can you test your program against a graph which is a path with 20000 nodes, with the node numbered 0 being a leaf and there being an edge from i to i+1? Please try to run it with stack size limits set to those on SPOJ(8MB IIRC) and ensure that you don't have a stack overflow. This is the worst case graph for the stack usage. If you do see the recursion being too deep, you can use a BFS instead to check that the number of connected components is 1. Alternately, you can use path compression, which will make your runtime O(n log n), but still easily fast enough to fit in the 1 second limit.

DFS - Checking Cycles

1 Answers