题解：P12371 【模板】最大团/最大独立集

hgckythgcfhk · 2025-04-30 03:04:52 · 题解

这个题我求助了 deepseek，学到了一种题解区目前没有的做法，而且这个做法的时间复杂度是还可以的。

由于团和独立集只要求个反图重新做一遍就可以了，这里只讨论团，独立集是同理的。

定义

极大团：可以类比函数的极值，如果一个团不能通过增加一个点来得到一个更大的团，则称这个团为极大团。

可以发现，最大团一定是极大团，而极大团不一定是最大团。

由暴力得到的启发

首先，最大团是 NP 问题，同时这题没让取模，根据经验告诉我们最大团的个数很可能是不多的，可以猜测 O(\text{最大团个数}) 的时间复杂度是能过的。

感性理解一下，如果两个团的异或的点集是一个团，则这两个团的并也是团，也就是说，所有最大团的异或不能是一个团，这保证了邻接矩阵中的 1 的数量不能太多，而为了尽可能构造比较多的最大团又不能太少，在两个比较矛盾的限制下最大团看起来不会太多。

这个结论先不证，放到后面证，先假设它是对的。

考虑最暴力的暴力，直接枚举二进制硬判，而一般情况下枚举二进制其实是对 dfs 的优化，而这个题枚举二进制实则更容易想到，但不可否认的是这个题可以 dfs。

大体说一下这种对集合 dfs 的一般形式，直接维护一个集合每次加入一个元素，加到不合法为止开始回溯。

这样虽然仍然可以卡到 O(2^n) 但实际上这样少枚举了很多东西，这启发我们这种枚举集合的形式方便减枝。

虽然上面说的这些对于大部分能来看这个题的人拿来说比较简单，但事实上我认为这属于思路的一步，而且 OIwiki 上就是从这个暴力开始讲起的。

Bron–Kerbosch 算法

为了方便描述，下面简称为 BK 算法，事实上 BK 算法就是对上面的暴力的优化，现在记 3 个集合：

先说算法流程：

初始化 R,X 为空集，P 为全集，也就是说，一开始团内没有任何东西，且所有点都被候选。
如果 P 和 X 都是空集，则此时 R 是一个极大团。
从 P 中枚举点 v，R 加上 v，和 P,X 分别与 v 的邻域的交，其中邻域表示与 v 相邻的点组成的点集。
将当前枚举的 v 从 P 移动到 X。

对于第三步，具体的，记 v 的邻域为 V，第三步相当于从 (R,P,X) 递归到 (R\cup v,P\cap V,X\cap V)。

BK 算法快的原因是每一步向某个极大团扩展的过程中，以状态为点以转移为边建图后，图是一棵树。也就是说，BK 算法的时间复杂度是和极大团个数同级的

下面证明这个算法正确性和时间复杂度。

首先我认为正确性和时间复杂度其实可以合并到一起证，具体分为一下两个方面：

完备性，即所有极大团都会被搜到。

我在学习了 deepseek 给出的很多证法没看懂，又在别的很多地方看到“显然”之后，突然想到一个好理解的解释来让这里“显然”，换一种暴力的思路，类似于枚举二进制，直接对每个点选不选进行 dfs，而这个只是相当于换了一个 dfs 的顺序，按在集合 P 中的位置排序，递归下去的那一步相当于选，而回溯后会把 v 移至 X，这正好就是不选。

那这优化了什么？在递归的过程中有取交集的一步，这样避免掉了候选一些明显不合法的点（考虑 P 的定义是候选点集），而实际做的其实是换了顺序后最暴力的暴力。

但是还有个不好理解的地方就是 X 的意义，这一点确实很多现成的资料里面有一定的误导性，如果你只需要枚举所有的极大团确实可以不用 X，实际上根本用不到这个集合，在 OIwiki 的伪代码中，不判的运行结果是一样的，而判这个地方只是为了要输出所有极大团时防止多输出一些非极大团，对于本题是没有影响的。

唯一性，即每个极大团只会被搜一遍。

这个其实根据上面说的那么多已经比较可以显然了，这其实相当于证状态之间的树形关系，从把 BK 算法理解成换顺序暴力的角度来看就很容易发现这个是对的，同时这保证了时间复杂度是和极大团个数同级，事实上可以构造极大团个数等于最大团个数且时间达到上界，所以之前假设的结论是对的。

然后就是极大团的个数了，根据 Moon-Moser 定理，极大团最多有 O(3^{\lfloor \frac{n}{3}\rfloor}) 个，同时这个是可以卡满的。

下面证明 Moon-Moser 定理，首先 n\le 3 的情况显然成立，这个自己构造一下就行，然后假设 k<n 的 k 成立，现在随便找一个邻域并上自己不是所有点的点，即邻域大小小于 n 的点 v 分讨。

包含 v 的极大团必须是 v 的邻域和 v 的并的子集而前面保证了邻域大小小于 n，所以这样的极大团最多有 O(3^{\lfloor \frac{n-1}{3}\rfloor}) 个。
不包含 v 的极大团只能从剩下的 n-1 个点里面找，这样的极大团最多也是 O(3^{\lfloor \frac{n-1}{3}\rfloor}) 个。
找不到这样的 v 时时完全图，极大团只有一个。

对于前两种，注意到下取整，直接加起来只会差 2 倍的常数，这样就归纳地证完了。

这个上界可以在完全三分图上卡满，完全三分图顾名思义就是分成三个集合后每个集合内部没边但每个点和其他两个集合的所有点之间有边。

基于 BK 算法的优化

这是根据上面的过程，写出来的程序：

unsigned n,m;
struct A{ull a[64],ans,cnt,sta;
    void ins(cit u,cit v){a[u]|=1ll<<v;}
    void chk(cit ll R){cit x=__builtin_popcountll(R);if(x<ans)return;if(x==ans){++cnt;return;}cnt=1,ans=x,sta=R;}
    void dfs(int ll P,int ll R){/*cerr<<bitset<8>(P)<<' '<<bitset<8>(R)<<'\n';*/if(!P)return chk(R);
        for(int ll v=__builtin_ctzll(P);P;P^=1ll<<v,v=__builtin_ctzll(P))dfs(P&a[v],R|1ll<<v);
    }void print(){cout<<ans<<' '<<cnt<<'\n';for(int i=1;i<=n;++i)if(sta&(1ll<<i))cout<<i<<' ';cout<<'\n';}
}G1,G2;Bool(a[64],64);ull all=0;
void init(){rd(n),rd(m);
    for(int u,v;m--;a[u][v]=a[v][u]=1)rd(u),rd(v);
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if((i^j)&& a[i][j])G1.ins(i,j);
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if((i^j)&&!a[i][j])G2.ins(i,j);
    for(int i=1;i<=n;++i)/*G1.ins(i,i),G2.ins(i,i),*/all|=1ll<<i;
}void solve(){init();
    G1.dfs(all,0);G1.print(),G2.dfs(all,0),G2.print();
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}

我认为我说的足够详细到能直接把程序写出来了，所以为了减少不必要的篇幅和过审，这里省略了缺省源。

这样是过不了的，能拿 42 分。

首先，先给出几个优化。

考虑到对于一组当前的 R 和 P，最优情况下也只能 P 全都加进 R 里，而我们要找的只是最大而不是所有极大团，所以这里可以根据当前答案减枝，只需要在判断 P 空后面加一行：
```
if(__builtin_popcountll(R|P)<ans)return;
```
就好了。这个减枝可以优化到 76 分。
递归时按邻域与 P 的交从大到小排序，注意只有这个优化是没用的，这个优化是辅助上一个减枝更快找到比较大的团以达到减掉更多没用的分支用的，因为看起来这样排序后较前的分支的候选点集减少的比较少，后面操作起来更自由所以更优，但这貌似有点负优化，实测 67 分，当然还有一种说法是按度数从大到小排序，虽然看起来不如上一个优但这个能 76 分。

我不知道是不是数据具有特殊性的问题，这个优化等于没有优化。

支配点减枝，就是如果有某个点 u 的邻域是另一个点 v 的邻域的子集，那 u 一定在 v 后搜，这个如果真有的话其实理论上能优化不少，但事实上想不增加太多额外开销写这个不好写，而且很容易卡的没有这样的支配点对，所以我没试。
颜色减枝，这是 deepseek 提供的思路，据说在稠密图上效果很好，但这个减枝貌似对后面没什么帮助，而且有额外开销，我看着不太好写所以就没试。

Tomita 改进

Tomita 的改进通过选择枢轴顶点（pivot）减少递归分支，显著提升效率。

枢轴的作用：

选择一个顶点 u 作为枢轴（通常选当前的 P|X 中度数最大的点）。

关键性质：所有极大团必须包含 u 或至少一个与 u 不相邻的点。

下面证明这个性质，假设存在极大团 C 不包含这样的点，那么 C\cap(P\setminus N(u))= \emptyset，则有 C\subset P\cap N(u)\cup X ，由于 C 不包含 u，则 C\subset P\cup X\setminus u，由于 C 一定不可能属于 X，那两个并上 X 可以消掉，所以发现 C\subset N(u)，即 u 到 C 所有点有边，则 C 不是极大团，矛盾。

于是这样就能过了，为防止因火车头导致无法过审，这里只放核心程序。

unsigned n,m;
struct A{ull a[64],ans,cnt,sta;
    void ins(cit u,cit v){a[u]|=1ll<<v;}
    void chk(cit ll R){cit x=__builtin_popcountll(R);if(x<ans)return;if(x==ans){++cnt;return;}cnt=1,ans=x,sta=R;}
    il unsigned find();
    void dfs(int ll P,int ll R,int ll X){/*cerr<<bitset<8>(P)<<' '<<bitset<8>(R)<<'\n';*/if(!P)return chk(R);
        if(__builtin_popcountll(R|P)<ans)return;
        int ll U=P|X,Q;int u=0;
        for(int ll v=__builtin_ctzll(U);U;U^=1ll<<v,v=__builtin_ctzll(U))if(__builtin_popcountll(a[v]&P)>__builtin_popcountll(a[u]&P))u=v;
        Q=P&~a[u];
        for(int ll v=__builtin_ctzll(Q);Q;Q^=1ll<<v,P^=1ll<<v,X|=1ll<<v,v=__builtin_ctzll(Q))dfs(P&a[v],R|1ll<<v,X&a[v]);
    }void print(){cout<<ans<<' '<<cnt<<'\n';for(int i=1;i<=n;++i)if(sta&(1ll<<i))cout<<i<<' ';cout<<'\n';}
}G1,G2;Bool(a[64],64);ull all=0;
void init(){rd(n),rd(m);
    for(int u,v;m--;a[u][v]=a[v][u]=1)rd(u),rd(v);
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if((i^j)&& a[i][j])G1.ins(i,j);
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)if((i^j)&&!a[i][j])G2.ins(i,j);
    for(int i=1;i<=n;++i)/*G1.ins(i,i),G2.ins(i,i),*/all|=1ll<<i;
}void solve(){init();
    G1.dfs(all,0,0);G1.print(),G2.dfs(all,0,0),G2.print();
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}

部分内容借鉴自 deepseek，但我并没有整段整句的复制粘贴，也没有原封不动的抄袭，事实上仅仅只是因为我没有学过这个算法使用 deepseek 进行学习正常的整理笔记。