这是一个最大独立集问题，是一个np完全问题，目前没有多项式时间内的确定性算法。我用的是最简单的回溯算法，没有剪枝的策略。就是顺序的考虑节点，考虑第一个节点能不能加入，分成两种情况，然后在前面的基础上考虑下一个节点。最差时间复杂度是指数级的，但是我跑出来是16ms。所以说，这道题的数据并不那么bt。
当然这道题可以转化为最大团问题，最大团问题有一个bk算法，带动态规划，效果应该会更好。

贴上我的代码和大家分享：

#include <stdio.h>
#include <stdlib.h>
#define MAXN 100

char graph[MAXN][MAXN];
int n;
int best[MAXN],best_n;
int cur[MAXN],cur_n;

void backtrack(int node)
{
    int i;
    if(node>=n)
    {
        if(cur_n > best_n)
        {
            for(i=0;i<cur_n;i++)
                best[i] = cur[i];
            best_n = cur_n;
        }
        return ;
    }

    for(i=0;i<cur_n;i++)
        if(graph[node][cur[i]])
            break;
    if(i==cur_n)
    {
        cur[cur_n++] = node;
        backtrack(node+1);
        cur_n--;
        backtrack(node+1);
    }
    else
        backtrack(node+1);

}

int main()
{
    int T;
    int k;
    int t1,t2;
    int i,j;

    scanf("%d",&T);
    while(T>0)
    {
        scanf("%d%d",&n,&k);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                graph[i][j] = 0;
        for(i=0;i<k;i++)
        {
            scanf("%d%d",&t1,&t2);
            graph[t1-1][t2-1] = 1;
            graph[t2-1][t1-1] = 1;
        }
        best_n = 0;
        cur_n = 0;
        backtrack(0);
        printf("%d\n",best_n);
        for(i=0;i<best_n;i++)
            printf("%d ",best[i]+1);
        printf("\n");
        T--;
    }

    return 0;
}