1 / 2
May 2005

Hi,
I am expecting a wrong answer but somehow for any thing like DFS or BFS it is giving me TLE. I am hardcoding direction as DFS ie dir=0 in my code still it is giving TLE.I guess Somewhere in reading data it is going into infinite loop because it is not finding a 0 0. Can you please check whether my code is incorrect or something about data ?

I am using only matrices i.e sparse matrices.

Like
1st column of each row=number of elements and then i store the vertices adjacent in each column.

I perform a recursive DFS
for each column (
if( not present in array_print)
{
store in array_print;
recursive(array_print-node)
}

For BFS

array_print=first node
for each column in the array_print (
if(not present in array_print)
add to array_print;

Below is my code. I tried inputs with given and the inputs at sphere.pl/~mima/spoj/problems/TDBFS/.
Everything was fine.


#include<stdio.h>
/* dir=0 is dfs and dir=1 is bfs in line 104. I am hardcoding it to dfs and expect a wrong answer . But it is giving me time limit execeeded. Is there any problem reading data */
int arr_print[1001],count=0,left=0,right=0;
/* arr_print is the array where the dfs or bfs is stored to print the output */
void print_array(int **ar,int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			printf(" %d",ar[i][j]);
    	printf("\n");
}
return;
}
static inline int isnotfound(int k) /* Checking whether the element is already in the arr_print . If not we generate the nodes as per dfs or bfs */
{
	int i;
	for(i=0;i<count;i++)
		if(arr_print[i]==k)
			return 0;
	return 1;
}
static inline void dfs(int **a,int row,int n,int level) /* recursive procedure for dfs . if XYZ are the vertices then dfs(X),dfs(Y),dfs(Z) */
{
	int i,j=1;
	if(count==n)
		return;
	else
	{
		for(j=1;j<=a[row][0];j++)
		{
			if(isnotfound(a[row][j]))
			{
				arr_print[count++]=a[row][j];
	//			printf("DEBUG::: %d %d\n",row,arr_print[count-1]);
				dfs(a,a[row][j],n,level+1);
			}
		}
	}
}
static inline void bfs(int **a,int row,int n,int level) /* BFS for adjacent veritices */
{
	int i,j;
	left=row;
	for(i=0;i<n && count<n;i++)
	{
		for(j=1;j<=a[arr_print[i]][0];j++){
			{
				if( isnotfound(a[arr_print[i]][j])){
					arr_print[count++]=a[arr_print[i]][j];
				}
			}
		}
	}
	return;
}
void initialize(int r)
{
	int **arr;
	int n,i,j,m,tmp,idx,dir;
	scanf("%d",&n);
	arr=calloc(n+1,sizeof(int *));
	arr[0]=calloc(n+1,sizeof(int));
	for(i=0;i<n;i++){
    		scanf("%d",&idx);
		scanf("%d",&m);
		arr[idx]=calloc(m+1,sizeof(int));
		arr[idx][0]=m;
	for(j=1;j<=m;j++)
	{
		scanf("%d",&tmp);
		arr[idx][j]=tmp;
	}

}
/*
	for(i=1;i<=n;i++){
	for(j=0;j<=arr[i][0];j++)
		printf("%d ",arr[i][j]);
	printf("\n");
	}
	*/
    printf("graph %d\n",r);
while(1)
{
	scanf("%d%d",&tmp,&dir);
	if(tmp==0 && dir==0)
		break;
count=0;

for(i=0;i<1001;i++)
	arr_print[i]=0;

arr_print[count++]=tmp;
dir=0;
if(dir==1)
	bfs(arr,tmp,n+1,0);
else
	dfs(arr,tmp,n+1,0);

for(i=0;i<count;i++)
	printf("%d ",arr_print[i]);
printf("\n");

}
free(arr);
}
int main()
{
	int no,i=0;
	scanf("%d",&no);
	while(no--){
	i++;
	initialize(i);
	}
	return 0;
}
  • created

    May '05
  • last reply

    May '05
  • 1

    reply

  • 170

    views

  • 2

    users

19 days later

hi,
many superflous things in your code. your problem is of algo nature, i
changed the function isnotfound from O(nodes) to O(1) and got ac:
177442 2005-05-28 10:21:10 Csaba Noszaly Searching the Graph accepted 23.25 11824 C
peace, csaba noszaly

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 14 6d

Want to read more? Browse other topics in C and C++ or view latest topics.