最大团相关问题 & 题解：P12371 最大团/最大独立集
Purslane
·
·
题解
Solution
显然最大独立集可以转为补图的最大团，所以只需要搞定最大团怎么找。
复杂度 O(n 2^{\frac{n}{2}}) 的最大团算法
考虑枚举团中编号最小的点 i，考虑剩下的 n-i 个点。
将其分为两部分 A 和 B。在 A 和 B 上分别做 O(2^{|S|}) 的指数级算法，得到内部所有可能的团。
这是一个高维前缀和问题，所以可以做到 $O((n-i) 2^{\frac{n-i}{2}})$。求和后还是 $O(n2^{\frac{n}{2}})$。
## 复杂度 $O(2^{\frac{n}{2}})$ 的最大团算法
其实复杂度瓶颈就在算高维前缀和上。
考虑高维前缀和的具体含义：对于集合 $S$，算出所有包含在 $S$ 中的团的信息，记为 $f_S$。
令 $u$ 为 $S$ 中任何一个元素，$T_u$ 为 $u$ 在 $S$ 中的邻域。
如果 $u$ 不在团中，由 $f_{S / \{u\}}$ 转移；如果 $u$ 在团中，由 $f_{T_u} + 1$ 转移。所以可以做到 $O(2^{\frac{n-i}{2}})$ 单次。求和后为 $O(2^{\frac{n}{2}})$。
## 复杂度 $O(\sqrt m 2^{\frac{\sqrt{2m}}{2}})$ 的最大团算法
其实没啥本质不同。类似三元环计数的手法，将所有点按照度数排序。这样可以控制每个点比他大且有连边的点个数在 $\sqrt {2m}$ 之内。跑和上面一样的方法即可。
根据琴生不等式（其实也不是琴生不等式，就是最基础的凸函数求最值），最大值为 $O(\sqrt m 2^{\frac{\sqrt{2m}}{2}})$。这种方法在稀疏图上非常优秀。
## 最大独立集的一个搜索做法
哎我去年学过这个东西，怎么给忘了呢。
如果所有点的度数都 $\le 2$，那么只有环和链，最大独立集是容易处理的。
考虑枚举度数最大的点是否在独立集里面，如果在就把其邻域内所有点都删掉。因此复杂度满足递推式 $T(n) = T(n-1) + T(n-4)$，得到 [$T(n) = O(1.3803^n)$](https://www.wolframalpha.com/input?i2d=true&i=Power%5Bx%2C4%5D%3DPower%5Bx%2C3%5D%2B1&lang=zh)。
哎我的 $O(2^{\frac{n}{2}})$ 怎么在代码难度和时间复杂度上都被偏序了。难过。
放一个 $O(2^{\frac{n}{2}})$ 的代码，略微卡常：
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=50+5;
struct INFO {int mx,cnt;ll ex;}F[(1<<25)+10];
INFO operator +(INFO A,INFO B) {if(A.mx>B.mx) return A;if(B.mx>A.mx) return B;return {A.mx,A.cnt+B.cnt,A.ex};}
INFO operator +(INFO A,ll S) {return A.mx+=__builtin_popcountll(S),A.ex|=S,A;}
int n,m;
ll T[MAXN],FF[MAXN];
int NXT2[MAXN],NXT1[MAXN],n1,n2,f1[(1<<25)+10];
ll idx[(1<<25)+10];
bool ok[(1<<25)+10];
INFO calc(int u) {
vector<int> nxt;
ffor(v,u+1,n) if(T[u]&(1ll<<v-1)) nxt.push_back(v);
n1=n2=0;
for(auto id:nxt) {
if(n2<=n1) NXT2[++n2]=id;
else NXT1[++n1]=id;
}
INFO ans={-1,0,0};
ffor(i,1,n) {FF[i]=0;ffor(j,1,n1) if(T[i]&(1ll<<NXT1[j]-1)) FF[i]|=(1<<j-1);}
F[0]={0,1,0};
ffor(i,1,(1<<n1)-1) {
int lb=(i&-i),id=NXT1[1+(int)log2(lb)];
F[i]=F[i-lb]+(F[FF[id]&i]+(1ll<<id-1));
}
ok[0]=1,f1[0]=(1<<n1)-1;
ffor(i,0,(1<<n2)-1) {
if(i) {
ok[i]=0;
int lb=(i&-i),id=NXT2[1+(int)log2(lb)];
if(ok[i-lb]&&((idx[i-lb])&T[id])==idx[i-lb]) ok[i]=1,f1[i]=f1[i-lb]&FF[id],idx[i]=idx[i-lb]|(1ll<<id-1);
}
if(ok[i]) ans=ans+(F[f1[i]]+idx[i]);
}
return ans+(1ll<<u-1);
}
INFO solve(void) {
INFO ans={-1,0,0};
ffor(i,1,n) ans=ans+calc(i);
return ans;
}
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
ffor(i,1,m) {
int u,v;
cin>>u>>v;
T[u]|=(1ll<<v-1),T[v]|=(1ll<<u-1);
}
auto ans=solve();
cout<<ans.mx<<' '<<ans.cnt<<'\n';
ffor(i,1,n) if(ans.ex&(1ll<<i-1)) cout<<i<<' ';
cout<<'\n';
ffor(i,1,n) T[i]=(1ll<<n)-1-(1ll<<i-1)-T[i];
ans=solve();
cout<<ans.mx<<' '<<ans.cnt<<'\n';
ffor(i,1,n) if(ans.ex&(1ll<<i-1)) cout<<i<<' ';
return 0;
}
```