uvaoj 208 how can i speed up my program

Question

why my program Time Limited Error? because of the sort? this is the question link text

#include <cstdio>
#include <cstring>

using namespace std;

int map[22][44];
int book[22];
int total;
int sum;
int way[22];
int tails[22]; 
int tail; 

void init()
{
 memset(map,0,sizeof(map));
 memset(book,0,sizeof(book));
 sum =0;
 memset(way,0,sizeof(way));
 way[1]=1;
 memset(tails,0,sizeof(tails));
}

void sort()
{
 int t;
 for (int i=1;i<=22;i++)
  {
   if (tails[i]==0)
    break;
   else
    {
     for (int j=1;j<=tails[i]-1;j++)
      for (int k=j+1;k<=tails[i];k++)
       {
        if (map[i][j] > map[i][k])
         {
          t = map[i][j];
          map[i][j]=map[i][k];
          map[i][k]=t;
         }
       } 
    }
  }
}

void dfs(int x,int y)
{
 if ((x < 1)||(x > 22))
  return;
 if (book[x]==1)
  return;
 //printf("%d \n",x);
 if (x == total)
  {
   sum++;
   for (int i=1;i<=y-1;i++)
   {
    printf("%d ",way[i]);
   }
   printf("%d",total);
   printf("\n");
   return;
  }
 tail = tails[x];
 for (int i=1;i<=43;i++)
  {
   book[x]=1;
   way[y]=x;
   dfs(map[x][i],y+1);
   book[x]=0;
  } 
}

int main()
{
 int temp1,temp2;
 //freopen("ex.in","r",stdin);
 //freopen("ex.out","w",stdout);
 int c = 0;
 while(scanf("%d",&total)!=EOF)
 {
 c++;
 printf("CASE ");
 printf("%d",c);
 printf(":");
 printf("\n");
 init();
 for (;;)
  {
   scanf("%d%d",&temp1,&temp2);
   if ((temp1 == 0)&&(temp2 == 0))
    break;
   else
    {
     tails[temp1]++;
     tail = tails[temp1];
     map[temp1][tail]=temp2;
     tails[temp2]++;
     tail = tails[temp2];
     map[temp2][tail]=temp1; 
    }
  }
  sort();
  dfs(1,1);
  printf("There are ");printf("%d",sum);printf(" routes from the firestation to streetcorner ");printf("%d",total);printf(".");
  printf("\n");
 }
 return 0;
}

Answer 1

For a start, you're accessing tails and map past the end. C++ arrays are zero-indexed, so the first element is 0, and the last valid elements are tails[21] and map[21][43].

Answer 2

Because your sorting algoritm is in worst-case O(n*n), you can use InnoSort for better worst-case complexity O(n*log(n)).

You are using C++ then use sort function from <algorithm> header to do this simplest.

Documentation you can find at http://www.sgi.com/tech/stl/sort.html