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

79愛的鼓勵 1訂閱站台

作法:DFS+BFS

不知道,有沒有人看得懂題意-  -

總之就是用DFS一直伸,邊把最長的方式記錄下來(同樣是最長的 走法有多種)

再來是,將這些走法,用BFS去找分枝,如果已經是最長鏈裡面的話,不理

取沒走過的任一點(沒標上記號),將有連接的點標上記號,直到這個分枝的全部標上記號

此時time++;繼續找下一個沒標上記號的...在把有連接的點標上記號time++;

將所有可能的走法.比較time 最後輸出MAX time!

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

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
short int map[2001][200]={0},flag[2001]={0},max=0,maptop[2001]={0},top;  
char appear[4000][2001]={0};   
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
void DFS(int now,int time,int n,int t)  
{  
  int a,b;  
  if(time>=max)  
   {   
     if(time==max)  
       {  
        top++;
         for(a=1;a<=n;a++)   
            appear[top][a]=flag[a];  
       }   
     else 
       {  
         top=0;  
         for(a=1;a<=n;a++)   
            appear[top][a]=flag[a];   
       }    
      max=time;  
   }     
  for(a=0;a<maptop[now];a++)  
   if(flag[map[now][a]]==0)  
    {  
      flag[map[now][a]]=1;  
      DFS(map[now][a],time+1,n,t);   
      flag[map[now][a]]=0;   
    }
}   

main()  
{  
 int n,m;  
 while(scanf("%d %d",&n,&m)==2&&n!=0)  
   {  
     int a,b,c;   
     int flagx,flagy;   
     for(a=0;a<m;a++)  
      {  
        flagx=input();
        flagy=input();
           map[flagx][maptop[flagx]]=flagy;  
           maptop[flagx]++;   
           map[flagy][maptop[flagy]]=flagx;  
           maptop[flagy]++;  
      }   
      int maxt=0;   
      max=0;top=0;   
      for(a=1;a<=n;a++)  
        {  
         flag[a]=1;
         DFS(a,1,n,1);  
         flag[a]=0;   
        }
      for(a=0;a<=top;a++)  
        {  
          int time=0;
            for(b=1;b<=n;b++)   
                if(appear[a][b]==0)  
                    {  
                      time++;
                      int queue[2001]={0},t1,t2,top=0;  
                      queue[0]=b;   
                      for(t1=0;t1<=top;t1++)  
                          {  
                            int nn=queue[t1];  
                            for(t2=0;t2<maptop[nn];t2++)
                               if(appear[a][map[nn][t2]]==0)  
                                 {  
                                    top++;  
                                    queue[top]=map[nn][t2];   
                                    appear[a][map[nn][t2]]=1;  
                                 }   
                          }   
                    }   
           if(time>maxt)    maxt=time;
        }   
       printf("%d %d\n",max,maxt);
      for(a=0;a<=n;a++)  maptop[a]=0;   
   }
 return 0;  
}