uva-193-图染色-枚举

　　题意:n个节点,可用描成黑色或者白色,黑节点和黑节点不能相连,问最多描出多少黑节点

#include <iostream>
#include <stdio.h>
#include<memory.h>
using namespace std;

#define null NULL
const int N = 110;
int final = -1;
int mindex[N];
int map[N][N];
int vis[N];
int res[N];
int n, m;

void read()
{
    int s, e;
    for (int i = 0; i < m; i++)
    {
        cin >> s >> e;
        map[s][mindex[s]++] = e;
        map[e][mindex[e]++] = s;
    }

}

void dfs(int cur, int total)
{
    if(final!=-1 && n-cur+1+total<=final)
    {
        //n-cur+1+total,表示把当前节点和后面的所有节点都描成黑色能达到的最大数
        return;
    }
    if (cur > n)
    {
        if (total > final)
        {
            final = total;
            int j = 0;
            for (int i = 1; i <= n; i++)
            {
                if (vis[i] == 1)
                {
                    res[j++] = i;
                }
            }
        }
        return;
    }
    int ok = 1;
    for (int i = 0; i < mindex[cur]; i++)
        if (vis[map[cur][i]] == 1)
        {
            ok = 0;
            break;
        }
    if (ok)
    {
        vis[cur] = 1;
        dfs(cur + 1, total + 1);
    }
    vis[cur] = 0;
    dfs(cur + 1, total);
}

int main(int argc, char* argv[])
{
    //freopen("C:\Users\zzzzz\Desktop\1.txt","r",stdin);
    int k;
    cin >> k;
    while (k--)
    {
        cin >> n >> m;
        memset(map, 0, sizeof(map));
        memset(mindex, 0, sizeof(mindex));
        memset(vis,0,sizeof(vis));
        read();
        final = -1;
        dfs(1, 0);
        cout<<final<<endl;
        cout<<res[0];
        for(int i = 1; i <final;i++)
            cout<<" "<<res[i];
        cout<<endl;
    }

    return 0;
}