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

79愛的鼓勵 1訂閱站台

作法:DFS

這題害我已經搞不懂Backtracking(窮舉)跟DFS(深度優先)的差別了

總之終止的條件很重要,一直搜尋下去會TLE...

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

#include<stdio.h>
#include<stdlib.h>
int map[101][101]={0},flag[101]={0};
int n,k;
int maptop[101]={0},way[101]={0},x,y,max;
void DFS(int now,int time)
{ 
  int a,find=0;
  if(time>max) {
                for(a=1;a<=n;a++)
                 way[a]=flag[a];
                max=time;
                }
  if(now>n||(n-now)+time+3<=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 t,a,b;
 scanf("%d",&t);
 while(t--)
  {
    scanf("%d %d",&n,&k);
    for(a=0;a<=n;a++) {maptop[a]=0;flag[a]=0;way[a]=0;}
    for(a=0;a<k;a++)
     {
       scanf("%d %d",&x,&y);
       map[x][maptop[x]]=y;
       maptop[x]++;
       map[y][maptop[y]]=x;
       maptop[y]++;
     }
    max=0;
    DFS(1,0);
    printf("%d\n",max);
    for(a=1;a<=n;a++)
     if(way[a]==1) printf("%d ",a);
     printf("\n");
  }
 return 0;
}