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;
}
