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

79愛的鼓勵 1訂閱站台

作法: DFS

嘗試所有可能...

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

#include<stdio.h>
#include<stdlib.h>
int map[201][201]={0},top[201]={0},color[201]={0};
int n,m;
int a,b,c,x,y,find;
void DFS (int now)
{
  if(now==n) {find=0;return;}
  if(find==0) return;
  int a,flagx=0,flagy=0;
  for(a=0;a<top[now];a++)
   {
      if(color[map[now][a]]==1) flagx=1;
      else if(color[map[now][a]]==2) flagy=1;
   }  
   if(flagx==0&&flagy==1)  
      {color[now]=1; DFS (now+1);}
   else if(flagx==1&&flagy==0) 
      {color[now]=2; DFS (now+1);}
   if(flagx==0&&flagy==0)
      {
        color[now]=1; DFS (now+1);
        color[now]=2; DFS (now+1);
      }
}
main()
{
 while(scanf("%d",&n)==1&&n!=0)
     {
       scanf("%d",&m);
       for(a=0;a<n;a++) {top[a]=0;color[a]=0;}
       for(a=0;a<m;a++)
         {
           scanf("%d %d",&x,&y);
           map[x][top[x]]=y;
           map[y][top[y]]=x;
           top[x]++;top[y]++;
         }
       find=1;
       DFS (0);
       if(find==0) printf("BICOLORABLE.\n");
       else printf("NOT BICOLORABLE.\n");
     }
 return 0;
}