ACM 193 193 - Graph Coloring
作法: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;
}
您好,
想請問這一行:(n-now)+time+3<=max是怎麼來的
我知道是終止條件,但想知道由來
(如果是一張全部都有相連的圖的話 應該可以用/2) 2009-08-17 19:24:14