難得解個題
做個筆記
給定一張圖
點可以塗黑或塗白，黑色不相鄰
求最多可以塗多少黑點
一開始自以為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");
}
}
