c++ - DFS - Checking Cycles -

the objective find whether undirected, unweighted graph tree, i.e. check whether contains edge. i'm using modified form of white-gray-black dfs algorithm(which given in cormen , on notes mentioned here: http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part1.pdf )

but somehow, doesn't work. worked once, resulted in run time error @ spoj (http://www.spoj.com/problems/pt07y/).

update: i'm getting wrong answer problem. code works sample test cases though.

test case fails:

10 9  1 2  2 3  3 4  4 5  5 6  6 4  6 7  7 8  8 9 

---

#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(); /* has backedge not tree, print no */                     }                 }         }      condition2(); /* not have backedge not tree print yes */   }  int main() {   long z; cin>>n>>z;   // for(int i=0; i<n; i++) /* **removed nested loop reduce runtime, eliminated tle** */ //     for(int j=0; j<n;j++) //        m[i][j]=0;  for(int i=0; < 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; } 

a graph tree if connected , e = v-1, e , v number of edges , nodes respectively. so, should able solve in o(v) time long check e==v-1 before launching dfs.

can test program against graph path 20000 nodes, node numbered 0 being leaf , there being edge i i+1? please try run stack size limits set on spoj(8mb iirc) , ensure don't have stack overflow. worst case graph stack usage. if see recursion being deep, can use bfs instead check number of connected components 1. alternately, can use path compression, make runtime o(n log n), still fast enough fit in 1 second limit.