Max Independent Set

此题还是比较巧妙的，值得花点时间。

最大独立集是指图上最大的节点集，内部没有节点间的边。首先最大独立集是最大团（max clique）的互补概念，补图（没边的节点间加边，去掉所有现有边）的最大clique，就是原图的最大独立集。所以我们首先把问题转化为求补图上的最大clique，这个是个更容易理解的问题。

因为 $N=40$ ，所以想到meet in the middle的办法，但此题的难点，在于在求出前后一半中的max clique之后，怎样进行合并。简单求出前后半个图各一个max clique肯定是不行的，因为最后整体的max clique不一定是这两个clique 组合而成的。所以我们需要有更多的中间结果。

在纸上画画可以发现，一种合并办法是：

这里 $S$ 是左侧图中的一个clique，设 $H$ 是 $S$ 在全图中的“公共邻居”，就是 $H$ 集合中每一点都有到 $S$ 每个点的边。那么如果我们可以找到 $H$ 中最大的clique $S'$ ，则 $S'$ 就是与 $S$ 可以合并的右侧图的clique了。因为 $S$ 和 $S'$ 都是clique，所以内部全部两两有边，而“公共邻居”的定义，使得他们互相间也两两有边，所以合并起来后也是 clique，而对于 $S$ 来说，容易证明 $S'$ 是在右侧图中能找到的最大clique。因此，对所有 $S$ 求合并后的最大clique，就是题目解了。

公共邻居的求法容易，见下方程序中common[]。

另外我们还需要快速求解在右侧子图中，一个节点集内最大的clique，设为 $f[H]$ ，其中 $f[]$ 和 $H$ 都用bitmask表示。这个用递推的方式来做，任选 $H$ 中的一个节点 $k$ ， $A_k$ 是 $k$ 的邻居集合，则有：

f[H] = \mathtt{popmax} (f[H \setminus k], f[A_k \cap H] \cup \{k\})

$\mathtt{popmax}()$ 是选两个bitmask中, $1$ 的位多的数返回。注意 $A_k$ 中不包含 $k$ ，所以 $A_k \cap H$ 一定是 $H$ 的真子集，因此用这个可以递推计算。具体见代码中generate()函数。

另外为了加速运算和简化代码，使用了一些位运算：

x & (-x)是x的二进制表示中最低位置的1.
__builtin_popcountll(x)返回x的二进制表示中为1的位的个数。
__builtin_ctzll(x)返回x的进进制表示中从最低位开始碰到1之前的0的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, m;
int gr[45][45];
ll adj[45];
vector<ll> ml, mr;      // ml[i]，subset i中最大的clique
vector<ll> common;      // common[i]: 左侧subset i对应的共同邻居
ll ans;
 
ll popmax(ll a, ll b) {
    return __builtin_popcountll(a) < __builtin_popcountll(b) ? b : a;
}
 
void generate(int l, int r, vector<ll> &f) {
    f.resize(1 << (r-l+1), 0);
    for (int i = 1; i < (1 << (r-l+1)); i++) {
        int d = i & (-i);           // i中最低位的1
        int c = __builtin_ctzll(d); // d后面有几个0
        f[i] = popmax(f[i ^ d], f[i & (adj[c + l] >> l)] | d);
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        gr[u][v] = gr[v][u] = 1;
    }
    for (int i = 0; i < n; i++)    // 补图
        for (int j = 0; j < n; j++) 
            if (!gr[i][j] && i != j)
                adj[i] |= 1ll << j;
 
    generate(0, n/2-1, ml);         // 生成左侧所有clique
    generate(n/2, n-1, mr);         // 生成右侧所有clique
    
    common.resize(1 << (n/2), 0);
    common[0] = (1ll << n) - 1;
    for (int i = 1; i < (1 << n/2); i++) {  // 哪些节点是左侧子集i的公共邻居
        int d = i & (-i);
        common[i] = common[i - d] & adj[__builtin_ctzll(i)];
    }
 
    // meet in the middle
    for (int i = 0; i < (1 << n/2); i++)
        ans = popmax(ans, (mr[common[i] >> (n/2)] << (n/2)) | ml[i]);
    
    printf("%d\n", __builtin_popcountll(ans));
    for (int i = 0; i < n; i++)
        if (ans & (1ll << i))
            printf("%d\n", i);
 
    return 0;
}