看著人家的代碼寫(xiě)就是不好，還錯(cuò)了好幾次，雖說(shuō)簡(jiǎn)單還是自己靠得住。雖然可以用最大團(tuán)求解，但直接枚舉就好了。
規(guī)模小，看這個(gè)題就知道是求最大獨(dú)立集，而最大獨(dú)立集+最小覆蓋集=定點(diǎn)個(gè)數(shù)，而原圖最大團(tuán)=補(bǔ)圖最大獨(dú)立集。各種性質(zhì)。
#include <stdio.h>
#include <string.h>
#define N 105
bool g[N][N], color[N], mk[N];
int n, m, ans;
bool ok(int u)
{
for(int i = 1; i <= n; i++)
{
if(g[u][i] && color[i]) return 0;
}
return 1;
}
void dfs(int u, int cnt)
{
if(u > n)
{
if(cnt > ans)
{
ans = cnt;
for(int i = 1; i <= n; i++) mk[i] = color[i];
}
return;
}
if(cnt + n - u + 1 <= ans) return;
if(ok(u))
{
color[u] = 1;
dfs(u + 1, cnt + 1);
color[u] = 0;
}
dfs(u + 1, cnt);
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
ans = 0;
memset(g, 0, sizeof(g));
memset(mk, 0, sizeof(mk));
memset(color, 0, sizeof(color));
scanf("%d %d", &n, &m);
for(int i = 0; i < m; i++)
{
int a, b;
scanf("%d %d", &a, &b);
g[a][b] = g[b][a] = 1;
}
dfs(1, 0);
printf("%d\n", ans);
bool flag = 1;
for(int i = 1; i <= n; i++)
{
if(mk[i])
{
if(flag) flag = 0;
else printf(" ");
printf("%d", i);
}
}
printf("\n");
}
return 0;
}