独立集是指图的顶点集的一个子集,该子集的导出子图不含边。

一个图中包含顶点数目最多的独立集称为最大独立集。

所以最大独立子集=图的补图的最大团

熟悉下模板：

 

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int t, n, m, g[101][101], g2[101][101], ans[101], num;

void jeo(int n, int *u, int mat[][101], int size, int &max, int &bb, int *res, int *rr, int *c)

{

    int i, j, vn, v[101];

    if (n)

    {

        if (size + c[u[0]]  <= max) return;

        for(i = 0; i < n + size - max && i < n; ++i)

        {

            for(j = i + 1, vn = 0; j < n; ++j)

                if (mat[u[i]][u[j]]) v[vn++] = u[j];

            rr[size] = u[i];

            jeo(vn, v, mat, size + 1, max, bb, res, rr, c);

            if (bb) return;

        }

    }else if(size > max)

    {

        max = size;

        for(i = 0; i < size; ++i)

            res[i] = rr[i];

        bb = 1;

    }

}

int jeogia(int n, int mat[][101], int *ret)

{

    int max = 0, bb, c[101], i, j;

    int vn, v[101], rr[101];

    for(c[i = n - 1]; i >= 0; i--)

    {

        for(vn = 0, j = i + 1; j < n; j++)

            if (mat[i][j]) v[vn++] = j;

        bb = 0;

        rr[0] = i;

        jeo(vn, v, mat, 1, max, bb, ret, rr, c);

        c[i] = max;

    }

    return max;

}

int main()

{

    scanf("%d", &t);

    while(t--)

    {

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

        memset(g, 0, sizeof(g));

        memset(g2, 0, sizeof(g2));

        while(m--)

        {

            int a, b;scanf("%d%d", &a, &b);

            a--; b--;

            g[a][b] = g[b][a] = 1;

        }

        for(int i = 0; i < n; i++)

            for(int j = 0; j < n; j++)

                if (!g[i][j]) g2[i][j] = 1;

        num = jeogia(n, g2, ans);

        printf("%d\n", num);

        for(int i = 0; i < num; i++)

        {

            if (i != num - 1) printf("%d ", ans[i] + 1);

            else printf("%d\n", ans[i] + 1);

        }

    }

    return 0;

}