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

79愛的鼓勵 1訂閱站台

作法:DFS

搜尋的終止條件很重要

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

#include<stdio.h>
#include<stdlib.h>
int map[256][256]={0},flag[256]={0};
int n,k;
int maptop[256]={0},way[256]={0},x,y,max;
void DFS(int now,int time)
{ 
  int a,find=0;
  if(time>max)  max=time;
               
  if(now>n||(n-now+1)/2+time+2<=max) return;

  for(a=0;a<maptop[now];a++)
   if(flag[map[now][a]]==1)
    {find=1;break;}
  if(find==0)
   {
     flag[now]=1;
     DFS(now+1,time+1);
     flag[now]=0;
   }
  DFS(now+1,time);
}
main()
{
 int a,b;
    scanf("%d",&n);
    for(a=0;a<=n;a++) {maptop[a]=0;flag[a]=0;way[a]=0;}
    while(scanf("%d",&x)==1&&x!=0)
    {
       scanf("%d",&y);
       map[x][maptop[x]]=y;
       maptop[x]++;
       map[y][maptop[y]]=x;
       maptop[y]++;
    }
    max=0;
    DFS(1,0);   
    printf("%d\n",max);
 return 0;
}