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/