# Is it a tree : Runtime Error

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;

}
``````
1 Like

long mat[10001][10001] = {0}; // is equivalent to long mat[100020001] = {0};

It is not possible to declare an array of that size. The maximum limit is around 10^6 to 10^7. Declaring an array of size 6*10^6 usually works for me in contests. You have to reconsider your approach. Try using an adjacency list or vector of vectors. Also, it is possible to solve it using a 1-D array of size 10001 and a 2-D array of size 10001x2 using DFS.

1 Like

I think that your array: mat[10001][10001] only has one value of {0; 1}, so you can declare it by boolean array, such as bool mat[10001][10001]. With boolean array, you can declare upto about 5 * 10^8 elements, with 2 * 10001^2, about 190 MB of memory, which is allowed on many judger like CodeChef.

upd: I’ve accepted, using boolean array with less than 100MB. ID of submission : 5262226

2 Likes

Thanks. It is working on Codechef but the same is returning a Wrong Answer on SPOJ. I thinking it is failing for the test Case 6.

1 Like

Can you give me a problem code on SPOJ?
But I saw that many submission for this problem on Codechef using “TEXT” compiler, just output “YES”, so I am not sure that testcases on codechef are exactly right.

Yes, I saw that too. Simply printing YES would give AC on CodeChef. SPOJ has correct testcases and it is also solvable using union find disjoint sets. SPOJ link http://www.spoj.com/problems/PT07Y/