作法:DFS

2007 NPSC G. 丁丁共和國 的翻版

C語言要過就要開相鄰矩陣,不過要看測資...不過我想2ms不太可能點會到10000,應該是唬人的。

找只有連結1個點的端點,作DFS深入(能走多遠就走多遠 並把最遠的距離紀錄下來)

/***********************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
short int map[10001][50]={0},flag[10001]={0},max=0,maptop[10001]={0};
void DFS(int now,int time,int top)
{
  if(time>max) max=time;
  int a,b;
  for(a=0;a<maptop[now];a++)
   if(flag[map[now][a]]==0)
    {
      flag[map[now][a]]=1;
      DFS(map[now][a],time+1,top);
      flag[map[now][a]]=0;
    }
}
main()
{
 int n;
 while(scanf("%d",&n)==1)
   {
     int a,b,c,start[10001]={0};
     int flagx,flagy;
     for(flagx=0;flagx<n;flagx++)
      {
        while(scanf("%d",&flagy)==1&&flagy!=-1)
          {
           map[flagx][maptop[flagx]]=flagy;
           maptop[flagx]++;
           map[flagy][maptop[flagy]]=flagx;
           maptop[flagy]++; 
           start[flagy]++;   
           start[flagx]++;  
          }
      }
      max=0;
      for(a=0;a<n;a++)
       if(start[a]==1)
        {
         flag[a]=1;
         DFS(a,0,n);
         flag[a]=0;
        } 
       printf("%d\n",max); 
      for(a=0;a<=n;a++)
         maptop[a]=0;
   }
 return 0;
}
/*
5
1 2 -1                            
3 -1                           
4 -1                        
-1                            
-1
6
1 -1
2 3 4 5 -1
-1
-1
-1
-1
*/