TLE in spoj 1436. Is it a tree

[spd_sof]

spoj.pl/problems/PT07Y/
Can somebody tell me why is it going beyond limits and the correct rectification.

[code]
#include<stdio.h>
#include<stdlib.h>
int vis[10010]={0};
char *V  [20010]={0};
struct edge
{
	int u;
	int v;
};
struct edge E[20010]={0,0};
void dfs(int x,int m,int n){
	vis[x]=1; //printf("%d ",x);
	for(int i=1;i<=n;i++){
	   if((V[x][i] ==1 || V[i][x] ==1) && vis[i]==0)
               dfs(i,m,n);	
    }
}
int main()
{
	int N,M,i,m;
	scanf("%d %d",&N,&M);		
   	m=M; // save M        
	if(M != N-1){
	printf("NO");
	return 0;
	}
    E[0].u= -1;
E[0].v=	-1;

  
for(i=1;i<=20010;i++)
	V[i]=(char*) calloc(sizeof(char),20010);	        


i=1;
while(M--){
 scanf("%d %d",&E[i].u , &E[i].v);
  V[E[i].u][E[i].v] = 1;
i++;	
}
  dfs(1,m,N);
//printf("\n");		//printf("\n%d",search(1,2,m));
//for(i=1;i<=N;i++) printf("%d",vis[i]);
 /*check vis */
 for(i=1;i<=N;i++){
   if(vis[i]==0) {printf("NO"); return 0;}
 }
printf("YES");
return 0;
}
[/code]

[leppyr64]

I assume that you're using V as an adjacency matrix. Why does it need to be 20000x20000? Why don't you just declare it as a 10000x10000 array? That way you don't waste time creating an array.

int adj[10000][10000];

Why bother passing m or n into your function? n is not going to change throughout the execution of your dfs, so declare it globally.

If you're using a boolean adjacency list then you don't need a struct for edges, just two integer values to read the input, u and v.

Remember every piece of code that you write impacts something. Spend more time planning, and less time writing code, verify that your solution works. Those are a few suggestions to get you started.

Feel free to post back once you've updated your code. Cheers!

[spd_sof]

@leppy Thank u for ur reply..

I am still having problems.... I have made all the modifications that u had suggested but i am still getting TLE....

Here is the modified code.

#include<stdio.h>
#include<stdlib.h>
int vis[10010]={0};
char V[10010][10010]={0};
int m,n;
void dfs(int x){
	vis[x]=1; //printf("%d ",x);
	for(int i=1;i<=n;i++){
	   if((V[x][i] ==1 || V[i][x] ==1) && vis[i]==0)
               dfs(i);	
    }
}
int main()
{
	int N,M,i,m;
	int u,v;	
	scanf("%d %d",&N,&M);		
   	m=M; // save M        
	n=N; 	
	if(M != N-1){
	printf("NO");
	return 0;
	}	
	while(M--){
	 scanf("%d %d",&u , &v);
	  V[u][v] = 1;
	}
    
  dfs(1);
//printf("\n");		//printf("\n%d",search(1,2,m));
//for(i=1;i<=N;i++) printf("%d",vis[i]);
 /*check vis */
for(i=1;i<=N;i++){
   if(vis[i]==0) {printf("NO"); return 0;}
 }
printf("YES");
return 0;
}

[leppyr64]

N has a constraint of 10^4. An O(N^2) algorithm will have a worst case of 10^8 operations. That's too much to run in 1s. You should use an adjacency list instead.

[spd_sof]

ok i will try....just tell me whether the recursive version if dfs will work or i have to shift to the iterative version using a explicit stack.

[leppyr64]

Since your algorithm with the adjacency list will be O(n+m) I wouldn't think that recursion would be an issue.

[spd_sof]

Thank u so much...the code finally got accepted after the changes that u had suggested........

Why is complexity with adjacency list O(V+E) and with adj matrix O(V*V) ..... I didnt get this point rest is fine.....cheers..

[leppyr64]

You V nodes in the graph and E edges.

The adjacency matrix is O(V^2). Each node is visited once(V), and after visiting a node you check all nodes to see if an edge exists(V).

The adjacency list of O(V+E). Each node is visited once(V), but the only edges that are checked are the one's that are incidental to that node. Each edge will be incidental to two nodes so it will be checked twice, but for complexity constant factors are factored out.

[spd_sof]

i got it now....thank u..... I will trouble next time .....