作法 : 97全國資訊學科能力競賽 3. 找關鍵人物 改編

利用DFS的特性,當退回來的時候紀錄該點下的所有節點數

#include<stdio.h>           
#include<stdlib.h>           
short int map[20001][300]={0},maptop[20001]={0};           
int used[20001]={0},T[20001]={0};     
int n;        
void DFS (int now,int last)           
{           
   int a;     
   for(a=0;a<maptop[now];a++)     
      if(used[map[now][a]]==0)     
         {     
           used[map[now][a]]=1;     
           DFS(map[now][a],now);     
           used[map[now][a]]=0;     
         }     
   T[last]+=T[now];     
}     
 
main()           
{           
   while(scanf("%d",&n)==1)           
       {           
          int a,b,c,x,y;     
          for(a=1;a<=n;a++) {T[a]=1;maptop[a]=0;}     
          for(a=0;a<n-1;a++)           
             {           
                scanf("%d %d",&x,&y);           
                map[x][maptop[x]++]=y;           
                map[y][maptop[y]++]=x;           
             }     
                used[1]=1;DFS(1,0);used[1]=0;    
          for(a=1;a<=n;a++)     
              printf("%5d-%5d\n",a,T[a]);
       }           
   return 0;           
}           
/*       
8       
1 2
1 3
3 4
3 7
3 8
4 6
4 5     
*/