Getting a run time error for the problem : Is it a tree
http://www.codechef.com/problems/PD31/
Can you please explain what am I doing wrong? I have checked other codes and tried doing a dry run but can’t seem to figure out the error.
Logic Used:
Using adjacency matrix to implement the graph.
I am checking for two conditions. If the number of edges!= No. of nodes -1 , I output NO directly. If this condition is satisfied, I use dfs to check for cycles. If the node has been visited already and is not the parent or the last node to have been visited, then there is a cycle.
#include<iostream>
#include<cmath>
using namespace std;
long m,n,i,j;
long mat[10001][10001] = {0};
long visited[10001] = {0} ;
int flag = 0;
int last = -1;
void dfs(long i)
{
//cout<<"dfs"<<i<<endl;
// cout<<last<<endl;
visited[i] = 1;
for(j = 1;j<=n;j++)
{ //cout<<"value of J"<<j<<endl;
if( i==j || j==last)
{
continue;
}
else
{
if(visited [j] == 1 && (mat[i][j] == 1 || mat [j][i] == 1))
{
//cout<<"here";
flag = 1;
return;
}
if(visited[j] == 0 && (mat[i][j] == 1 || mat [j][i] == 1))
{
last = i;
dfs(j);
}
}
}
}
int main()
{
long i,u,v;
cin>>n>>m;
for(i=0;i<m;i++)
{
cin>>u;
cin>>v;
mat[u][v]=1;
mat[v][u]=1;
}
if(m != (n-1))
{
cout<<"NO";
return 0;
}
last =1;
dfs(1);
if(flag == 1)
cout<<"NO"<<endl;
else cout<< "YES"<<endl;
}