摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:DFS

找端點作DFS搜尋

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

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
short int map[2001][50]={0},flag[2001]={0},max=0,maptop[2001]={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,t;
 scanf("%d",&t);
 while(t--)
   {
     scanf("%d",&n);
     int a,b,c,start[2001]={0},top=0;
     char xx[101],yy[101],name[2001][50]={0};
     while(1)
      {
        scanf("%s %s",xx,yy);
        if(strlen(xx)==1&&xx[0]=='=') break;
        int a,b,c,m=strlen(xx),flagx,flagy,x[50]={0},y[50]={0};
        for(a=0;a<m;a++) x[a]=xx[a];
        for(b=0;b<top;b++)
         {
           for(a=0;a<50;a++)
            if(x[a]!=name[b][a]) break;
           if(a==50) {flagx=b;break;}
         }
        if(b==top)
         {
           for(a=0;a<m;a++)
            name[top][a]=x[a];
           flagx=top;top++;
         }
        m=strlen(yy);
        for(a=0;a<m;a++) y[a]=yy[a];
        for(b=0;b<top;b++)
         {
           for(a=0;a<50;a++)
            if(y[a]!=name[b][a]) break;
           if(a==50) {flagy=b;break;}
         }
        if(b==top)
         {
           for(a=0;a<m;a++)
            name[top][a]=y[a];
           flagy=top;top++; 
         }
         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;
}