[ACM] 193 : Graph Coloring

難得解個題
做個筆記

給定一張圖
點可以塗黑或塗白，黑色不相鄰
求最多可以塗多少黑點

一開始自以為greedy的直覺
"既然要塗最多黑色，那就把連結數最少的點塗黑吧，然後一路塗完..."
都說是自以為了，理所當然是錯的
google "ACM 193" 前幾個連結就有在討論這個，也有人提出了反例

所以只好乖乖暴力法了
暴力法的想法
"一個點非黑即白  所以只要把一個點塗黑 繼續塗完整張圖，
                               或者塗白 繼續塗完整張圖"
就可以找到所有結果

擺明可以遞迴，所以就遞迴求解

遞回函式的想法大概是
1. 選定還沒塗色的點，塗黑，並把相鄰點塗白   剩下的點遞迴求解
2. 把剛剛這個點塗白，遞迴求解
3. 整張圖都塗色了，判斷是否為最大值



code :

#include 
int n,k;
int graph[101][101];
int max;
int maxList[101];
int color[101];

void draw(){
 int finish = 1;
 int current[101];

 for(int i = 1; i <= n; ++i){
  current[i] = color[i];
 }
 for(int i = 1; i <= n; ++i){
  if(color[i] == 0){
   finish = 0;
   
   color[i] = 2; 
   for(int j = 1; j <= n; ++j){
    if(graph[i][j] == 1 && color[j] == 0){
     color[j] = 1;
     
    }
   }
   draw();
   color[i] = 1;
   for(int j = 1; j <= n; ++j){
    color[j] = current[j];
   }
   color[i] = 1;
   
  }
 }
 
 if(finish == 1){
  int count = 0;
  for(int i = 1; i <= n; ++i){
   if(color[i] == 2){
    ++count;
   }
  }
 
  if(count > max){
   max = count;
   count = 0;
   for(int i = 1; i <= n; ++i){
    if(color[i] == 2)
     maxList[count ++] = i;
   }
  }
 }
}

int main(){
    int c;

    scanf("%d", &c);

    for(int i = 0; i < c; ++i){
   
  max = 0;
  for(int x = 1 ; x < 101; ++x){
   maxList[x] = 0;
   color[x] = 0;
   for(int y = 1 ; y < 101; ++y)
    graph[x][y] = 0;
  }

        scanf("%d%d", &n, &k);

        for(int j = 0; j < k; ++j){
            int to , from;
            scanf("%d%d", &to, &from);

            graph[to][from] = 1;
            graph[from][to] = 1;
        }
  draw();
  
  printf("%d\n", max);
  printf("%d", maxList[0]);
  for(int i = 1; i < max; ++i)
   printf(" %d", maxList[i]);
  printf("\n");
 }
}