Is it a tree : Runtime Error

Getting a run time error for the problem : Is it a tree

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.


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<<last<<endl;
    visited[i] = 1;
    for(j = 1;j<=n;j++)
    { //cout<<"value of J"<<j<<endl;

        if( i==j || j==last)
            if(visited [j] == 1 && (mat[i][j] == 1 || mat [j][i] == 1))
                flag = 1;
            if(visited[j] == 0 && (mat[i][j] == 1 || mat [j][i] == 1))

                last = i;


int main()

long i,u,v;


if(m != (n-1))
    return 0;

last =1;

if(flag == 1)
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


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