最大团

_InRedBrother_QWQ_ · 2026-01-15 17:24:52 · 算法·理论

最大团

简介一下：给出一个 n 个点 m 条边的无向无边权图，求其中最大团的节点个数。

团的定义：\forall u, v \in 该团，u、v 间一定有连边。

数据范围：n \in [1, 35], m \in [1, \frac{(n - 1) \times n}{2}]。

大方向：状态压缩问题

几十几十的值域，只有三种潜台词：

搜索多写几层；
DP 状态多开几维；
可以用一个二进制整数压缩状态。

搜索的方法，详见一哥们的代码：

:::info[一哥们的代码]

//若两个点在同一团中，则这两个点在其反图中无连边
#include<bits/stdc++.h>
#define int long long
namespace FastIO{
    template<typename T>inline void read(T &x){
        x=0;int f=1;char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
        for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
    }
    template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
    template<typename T>void print(T x){
        if(x<0)x=-x,putchar('-');
        if(x>9)print(x/10);
        putchar(x%10^48);
    }
}
using namespace FastIO;
using namespace std;
const int N=40;
int n,m,ans,now;
bool ing[N];
set<int>s[N];
void dfs(int u){
    if(u>n){
        ans=max(ans,now);
        return;
    }
    bool f=true;
    for(auto v:s[u]){
        if(ing[v]){
            f=false;
            break;
        }
    }
    if(f){
        now++;
        ing[u]=true;
        dfs(u+1);
        now--;
        ing[u]=false;
    }
    if(n+(now-u)>=ans){
        dfs(u+1);
    }
}
signed main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            s[i].insert(j);
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;
        read(u,v);
        s[v].erase(u);
    }
    dfs(1);
    print(ans);
}

:::

这里考虑状压，不过 2^{35} 超过了 10^{8}，不能直接用以枚举，所以考虑状态压缩时，分成前一半的点 i \in [1, \left \lfloor \frac{n}{2} \right \rfloor]和后一半的点 j \in [\left \lfloor \frac{n}{2} \right \rfloor + 1, n]。这样，每次压缩的状态最多为 2^{18}，更为方便处理。

左右分别处理团

有分就有和。将 n 个点分开处理倒是好办，不过这要如何联系到答案的统计呢？

我们想到，一个大团一定可以看作两个小团，小团之间的每一个点又都有边相连。那么我们可以事先处理出分居左侧的所有点中的所有团、和分居右侧的所有点中的所有团，最后考虑合并统计答案。

找团，好办。枚举状态 I，检查 I 是否为团。

为此，我们要事先预处理所有分居左侧的点 i，将点 i 所有连出去的边的终点中，分居于左侧的终点压缩成一个整数，存放作为边集 Lef_{2^i}；所有分居右侧的点 j 亦然，存放作为边集 Rit_{2^j} 。

:::success[实现]

    cin >> n, L = n / 2 + 1, R = n - L;
    cin >> m;
    for(int i = 1; i <= m; i ++) {
        cin >> a >> b;

        if(b <= L) Lef[1 << (a - 1)] |= (1 << (b - 1)), Lef[1 << (b - 1)] |= (1 << (a - 1));
        if(a > L) Rit[1 << (a - L - 1)] |= (1 << (b - L - 1)), Rit[1 << (b - L - 1)] |= (1 << (a - L - 1));
        if(a <= L && b > L) L_R[1 << (a - 1)] |= (1 << (b - L - 1));
    }

时间复杂度 O(m)。

:::

这样，枚举位于左侧的点集 I，找到每一个 i \in I，判断他的边集 Lef_{2^i} 是否严格包含 I 就行；枚举位于右侧的点集 J 亦然。

:::success[实现]

    for(int I = 1; I < (1 << L); I ++) {
        int dI = I, i, f = 1;
        while(dI) {
            i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
//          cerr<<"Lef["<<i<<"]:"<<Lef[i]<<"; "<<I<<"\n";
            if((Lef[i] | I) ^ Lef[i]) {f = 0; break;}
        }

        if(f) canL[I] = true, can.emplace_back(I);
//      cerr<<I<<" "<<f<<"\n";
    }
    for(int J = 1; J < (1 << R); J ++) {
        int dJ = J, j, g = 1;
        while(dJ) {
            j = dJ - (dJ & (dJ - 1)), dJ = (dJ & (dJ - 1));
            if((Rit[j] | J) ^ Rit[j]) {g = 0; break;}
        }

        if(g) canR[J] = true;
    }

时间复杂度 O(2^L \times L)。

:::

:::info[关于我为什么不将边集存在 Lef_i 中，而要存在 Lef_{2^i} 中]

原因很简单：当时我还不会 __builtin_ctz(i) + 1 这种手段，就只能每次取出一个 2^i，代表 i 位置的状态为 1。

        int dI = I, i, f = 1;
        while(dI) {
            i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
            if((Lef[i] | I) ^ Lef[i]) {f = 0; break;}
        }

所以为了方便调用，就选择这样存储的。实际上用空间复杂度换取代码整洁度与时间复杂度。

:::

合并

此时，我们手握分别分居左侧与右侧的所有团，那么我们选择枚举左边的团再枚举右边的团两两配对……吗？恐怕过不去。

所以，引入另一个点集 L\_R_{2^i}，表示分居左侧的点 i 所有连出去的边的终点中，分居于右侧的终点压缩成的一个边集。

那么我们枚举分居左侧的每一个团 I，用它所含的每一个点的 L\_R_{2^i} 值与起来求得一个分居右侧的点集 I_1，判断起是否为一个团，更新答案。

不过想到，如果 I_1 并非一个团，而它的某些子集是团，这样倒是也可以更新答案。所以还要再枚举 I_1 的子集。

:::success[实现]

    for(auto I : can) {
        int dI = I, i, J = (1 << R) - 1;
        while(dI) {
            i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
            J = (J & L_R[i]);
        }

        int dJ = J;
        while(dJ) {
            if(true == canR[dJ]) ans = max(ans, num[I] + num[dJ]);
            dJ = (dJ - 1) & J;
        }
    }

时间复杂度 O(3^L)。

:::

总体来说，很悬但由于常数优秀，且测评机性能较好，最终过了。

总体实现

#include <bits/stdc++.h>
#define int long long
using namespace std;

int t = 1;

const int N = 35 + 5, M = 595 + 5, INF = 262144 + 10;
int n, L, R;
int m, a, b;
int Lef[INF], Rit[INF], L_R[INF];
bool canL[INF], canR[INF];
vector <int> can;

int num[INF];
void prepar() {
    for(int I = 0; I < INF; I ++) {
        int dI = I;
        while(dI) num[I] ++, dI = (dI & (dI - 1));
    }
    for(int i = 0; i <= 18; i ++) {
        Lef[1 << i] |= (1 << i), Rit[1 << i] |= (1 << i);
    }
}

int ans;

void solve() {
    cin >> n, L = n / 2 + 1, R = n - L;
    cin >> m;
    for(int i = 1; i <= m; i ++) {
        cin >> a >> b;

        if(b <= L) Lef[1 << (a - 1)] |= (1 << (b - 1)), Lef[1 << (b - 1)] |= (1 << (a - 1));
        if(a > L) Rit[1 << (a - L - 1)] |= (1 << (b - L - 1)), Rit[1 << (b - L - 1)] |= (1 << (a - L - 1));
        if(a <= L && b > L) L_R[1 << (a - 1)] |= (1 << (b - L - 1));
    }
//  for(int i=0;i<L;i++)cerr<<i<<"::"<<Lef[(1<<i)]<<"\n";
//  for(int j=0;j<R;j++)cerr<<j<<"::"<<Rit[(1<<j)]<<"\n";
//  for(int i=0;i<L;i++)cerr<<i<<"::"<<L_R[(1<<i)]<<"\n";

    for(int I = 1; I < (1 << L); I ++) {
        int dI = I, i, f = 1;
        while(dI) {
            i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
//          cerr<<"Lef["<<i<<"]:"<<Lef[i]<<"; "<<I<<"\n";
            if((Lef[i] | I) ^ Lef[i]) {f = 0; break;}
        }

        if(f) canL[I] = true, can.emplace_back(I);
//      cerr<<I<<" "<<f<<"\n";
    }
    for(int J = 1; J < (1 << R); J ++) {
        int dJ = J, j, g = 1;
        while(dJ) {
            j = dJ - (dJ & (dJ - 1)), dJ = (dJ & (dJ - 1));
            if((Rit[j] | J) ^ Rit[j]) {g = 0; break;}
        }

        if(g) canR[J] = true;
    }

    for(auto I : can) {
        int dI = I, i, J = (1 << R) - 1;
        while(dI) {
            i = dI - (dI & (dI - 1)), dI = (dI & (dI - 1));
            J = (J & L_R[i]);
        }

        int dJ = J;
        while(dJ) {
            if(true == canR[dJ]) ans = max(ans, num[I] + num[dJ]);
            dJ = (dJ - 1) & J;
        }
    }

    cout << ans;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    prepar();

//  cin >> t;
    while(t --) solve();
    return 0;
}

最后

其实本题主要是为了学习“分成两半再合起来”这个trick。

事后教练说本题有其他优化，不过被细心的同学证伪了。

（教练：诶，AI 几爷子改了一中午没发现这是错的嘞？）

所以不要依赖于 AI。