CS C++ Code

Clique 团

Bron-Kerbosch Algorithm 最大团搜索算法

Wikipedia

OI-Wiki

概念

团(Clique)：一个无向图里面的一组顶点，其中任意两个顶点之间都有一条边相连（完全子图）

极大团(Maximal Clique)：是指一个团，无法通过添加任何新的相邻顶点来扩展它，可以理解为一个图里面的“饱和”团

最大团(Maximum Clique)：是指图中顶点数最多的团（可能有多个）

$\text{Maximum Clique} \subset \text{Maximal Clique}$

Bron-Kerbosch算法可以找到图中所有的极大团

三个重要的集合：

$R$：当前正在构建的团的集合
$P$：可能扩展$R$的候选项点的集合（与$R$中所有顶点相连）
$X$：已经处理过的顶点的集合（避免重复）

轴顶点(Pivot)：一般是指在算法中选取的关键节点或者结构作为“支点”，可以高效地分解或遍历问题，可以剪枝。这里是从$P \cup X$中选择的一个顶点，通常选择邻居最多的顶点（度数最大）

轴优化(Pivoting)思想：如果某个顶点$u$的邻居已经被处理过，那么它的所有邻居顶点$v \in N(u)$会在其他分支中被处理，当前分支无需重复计算。因此，只需要处理$P\backslash N(u)$，从而减少递归调用的次数。

代码示例

Python代码示例：

from collections import defaultdict

# 读图函数
def read_graph():
    first_line = input().strip()
    n, m = map(int, first_line.split())
    
    graph = defaultdict(set)
    
    for _ in range(m):
        u, v = input().strip().split()
        graph[u].add(v)
        graph[v].add(u)
        
    return graph

def bron_kerbosch_pivot(graph):
    def bk(R, P, X):
        # 如果P和X都是空的，说明R这个团已经是极大团了
        if not P and not X:
            cliques.append(R)
            return
        
        # 选择轴顶点：从P∪X中选邻居最多的顶点
        pivot = max(P.union(X), key = lambda v: len(graph[v]))
        # 只需要处理P中不属于轴顶点邻居的顶点
        for v in P.difference(graph[pivot]):
            neighbors = graph[v]
            bk(R | {v}, P & neighbors, X & neighbors)
            P.remove(v)
            X.add(v)
    
    cliques = []
    bk(set(), set(graph.keys()), set())
    return cliques

if __name__ == "__main__":
    graph = read_graph()
    for node in graph:
        print(f"{node}: {graph[node]}")

    BK_graph = bron_kerbosch_pivot(graph)
    print(BK_graph)

C++代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 10001
using namespace std;

int n, m;
vector <int> G[MAXN], maxClique;
int maxCliqueSize = 0;

//二分判断两个点是不是邻居
bool isNB(int u, int v)
{
    return binary_search(G[u].begin(), G[u].end(), v);
}

void BK(vector <int> &R, vector <int> &P, vector <int> &X)
{
    //如果P和X都是空的，说明R这个团已经是极大团了
    if(P.empty() && X.empty())
    {
        if(R.size() > maxCliqueSize)
        {
            maxCliqueSize = R.size();
            maxClique = R;
        }
        return;
    }

    //选择轴顶点：从P∪X中选邻居最多的顶点，记为u
    vector <int> PUX = P;
    PUX.insert(PUX.end(), X.begin(), X.end());
    int u = -1, maxDeg = -1;
    for(int v : PUX)
    {
        int deg = 0;
        for(int w : P)
            if(isNB(v, w)) deg++;
        if(deg > maxDeg)
        {
            maxDeg = deg;
            u = v;
        }
    }

    //将不属于轴顶点邻居的点加入到cand候选列表里
    vector <int> cand;
    for(int v : P)
        if(!isNB(u, v)) cand.push_back(v);
    
    //只需要处理候选列表里的点
    for(int v : cand)
    {
        vector<int> R2 = R, P2, X2;
        R2.push_back(v);
        for(int w : P)
            if(isNB(v, w)) P2.push_back(w);
        for(int w : X)
            if(isNB(v, w)) X2.push_back(w);
        
        BK(R2, P2, X2);

        P.erase(find(P.begin(), P.end(), v));
        X.push_back(v);
    }
}

int main()
{
    cin >> n >> m;
    for(int x = 1; x <= m; x++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int x = 1; x <= n; x++) sort(G[x].begin(), G[x].end());

    vector <int> R, P, X;
    for(int x = 1; x <= n; x++) P.push_back(x);

    BK(R, P, X);

    for(int v : maxClique) cout << v << " ";
    cout << endl;
    return 0;
}

[Python 3.12.5]
Sample Input:
5 6
A B
B C
B D
C E
D E
A D

Sample Output:
A: {'B', 'D'}
B: {'A', 'C', 'D'}
C: {'B', 'E'}
D: {'B', 'A', 'E'}
E: {'C', 'D'}
[{'B', 'C'}, {'B', 'A', 'D'}, {'E', 'C'}, {'E', 'D'}]

这里能看到，B A D就是唯一的最大团，其余也都是极大团

[C++]
Sample Input:
8 15
1 2
1 3
1 4
1 5
1 8
2 3
2 4
2 5
3 4
3 5
4 5
4 6
4 8
5 6
5 7

Sample Output:
4 1 2 3 5

除了Pivoting优化之外，还有Ordering优化

Ordering Heuristics for k-clique Listing

概念

$\omega$: The maximum clique size 图中最大团的大小，用于描述图的局部紧密性

$\alpha$: Arboricity 荫度，将图的边集分成尽可少的森林（无环图）所需要的最小数量，用于描述图有多“近似树结构”，图的稀疏性

$\eta$: h-index 图中存在$h$个顶点，使得每个顶点的度数都$\geq h$，用于刻画图中“高连接”顶点的聚集程度，描述图的局部集中度

$\Delta$: Maximum degree 图中所有顶点的最大度数，用于最坏情况分析

$\delta$: Degeneracy 退化度，图中任意非空子图的最小度数的最大值，用于度量图的稀疏程度

排序启发式的核心作用

通过控制节点的处理顺序和修建策略，显著减少无效搜索路劲，提升k-clique的效率

主要的排序启发式方法有以下三种：

Degree Ordering 度排序
- 按节点的度数排序
- 适用于稀疏图（？）
Degeneracy Ordering 退化排序
- 基于Core Decomposition（核心分解）生成排序，确保每个节点的后续邻居不超过图的退化度
- 比度排序更高效，尤其是在稠密图中表现更好
Color Ordering 颜色排序
- 通过贪心图着色方法为节点分配颜色，再按照颜色值排序
- 还可以结合退化排序和颜色修建优化

论文横向对比了不同的方法，并通过实际数据来评估，具体内容可以参考论文第三页的Table 1，已经很详细了

Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches

标题大意：在二分图中枚举所有满足遗传性凝聚性的子图：基于轴顶点的方法

本文中的$C_U$与$C_V$，和一开始的$P$是一样的，都是候选集合

概念

遗传性（Hereditary）：图的某种性质在子图中仍然保持

凝聚性（Cohesive）：图中节点之间连接紧密，比如高密度或高连通度，可能是Clique、k-cores之类的

二分图（Bipartite Graph）：图的节点可以划分为两个不相交集合，且所有边只在不同集合的节点之间连接（A-B）

二部团（Biclique）：在一个二分图中，二部团是指两个顶点集合$U’ \subseteq U$和$V’ \subseteq V$，期中每个$u \in U’$和每个$v \in V’$都有一条边连接。也就是说，$U’$和$V’$之间的连接是“饱和”，每个点都连到了对方集合中的所有点

k-双极团（k-biplex）：是一种“近似Biclique”。一个二分图中的顶点子集对$(U’,V’)$是一个k-biplex，如果满足：

$\forall u \in U’$，它最多可以不与$V’$中的k个点相连
$\forall v \in V’$，它最多可以不与$U’$中的k个点相连，

近似团（Approximate Clique）：用于描述“几乎完全”的子图结构，允许少量缺失边或松散连接，因为有时候完全团要求太高，难以扩展。常见的类型有如k-plex，k-clique，$\gamma$-quasi-clique，s-clique等

$\mathcal{P}$: Property 性质

枚举$\mathcal{P}-\text{subgraphs}$的基础框架

论文第五页的Algorithm 1，他能在二分图中枚举出所所有具有性质$\mathcal{P}$的子团，通过枚举二分图左边和每一个分支、二分图右边的每一个分支

前面有提到这是一个NP-hard的问题，时间复杂度是非常大的，最差时间复杂度能达到$O(f(n)*2^n)$，$f(n)$指的是生成candidate sets和exclusion sets的时间，因为要遍历整个图的每一个子图。所以可以用到Pivot优化

General Pivoting Rule: 在一个递归里面，$u \in C_U \cup X_U$是一个轴节点，然后$(P_U \subseteq C_U, P_V \subseteq C_V)$在扩展$(R_U, R_V)$的时候被略掉当且仅当任何一个包含$(R_U, R_V)$但不是$u$的结果不被$G(R_U \cup P_U, R_V \cup P_V)$包含

相对应的，$v \in C_V \cup X_V$也能别选做轴节点

我们有了这个轴节点，比如说$u$，然后掠过$(P_U \subseteq C_U, P_V \subseteq C_V)$之后，任何一个最大的包含$(R_U, R_V)$的$\mathcal{P}-\text{subgraph}$一定符合下面三种情况中的一种：

包含$u$
不包含$u$，但至少包含$C_V\backslash P_V$中的一个节点
不包含${u} \cup C_V\backslash P_V$，但包含$C_U \backslash (P_U \cup {u})$中的一个节点

具体实现伪代码参考Algorithm 2

虽然这个时间复杂度还是$O(f(n)*2^n)$，但实际上很多不必要的递归被剪枝了，在实际应用中有相对较好的表现

Efficient Maximum s-Bundle Search via Local Vertex Connectivity

标题大意：基于局部顶点联通性的高效最大s-Bundle搜索

概念

s-Bundle：

The 𝑠-bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than 𝑛 − 𝑠 vertices are removed, where 𝑛 is the number of vertices inside.

s-bundle作为一个有结合力的子团模型，比clique更松。一个图，如果他删掉少于n-s个节点还能保持连接，我们称这个图为s-bundle，n是这个图的节点数。

s-bundle强调连通性。根据已有的实验，s-bundle比其他的近似团，例如s-plex、s-block，在社区搜索方面有更突出的效果

An effective branch-and-bound algorithm for the maximum s-bundle problem

Existing examples of relaxed cliques include s-plex , s-defective clique , and quasi-clique and s-club which are defined by relaxing the vertex degree, edge number, edge density, and pairwise distance of vertices, respectively.

现有的relaxed clique的例子包括s-plex（放松度数）, s-defective clique（放松边数）, quasi-clique（放松边的密度）和s-club（放松节点之间的距离）

A vertex cut of a connected graph G is a subset of vertices in which, upon removal of these vertices and their incident edges from G, the remaining graph becomes a disconnected or trivial graph (a 1-vertex graph).

Vertex Cut: 一个连接图的vertex cut是一个子集，移除这些子集的节点和相连的边，剩下的图形成了一个断连图或者只剩下一个节点

从这个角度出发，根据Menger’s Theorem，s-bundle就是一个n个结点的图G，其任何一个vertex cut的大小都至少为n-s

Maximal s-bundle

根据BK算法和网络流路径查找验证s-bundle写了一份能枚举图中所有maximal s-bundle的代码，但时间复杂度极高，作为第一版

#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;

int n, m;
vector <int> G[MAXN];


// BFS － 只判是否存在一条容量>0 的路径，并记录父亲
bool bfs(int s, int t,
    const vector<vector<int>>& adj,
    vector<vector<int>>& cap,
    vector<int>& parent)
{
    fill(parent.begin(), parent.end(), -1);
    queue<int> q;  q.push(s);
    parent[s] = s;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (cap[u][v] > 0 && parent[v] == -1) {
                parent[v] = u;
                if (v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

// 判定集合 R 是否为 s‑bundle
bool isSB(const vector<int>& R, int s)
{
    int k = (int)R.size() - s;
    
    if (k == 0) return true;           // k = 0 总是成立
    if (k == 1){                       // k = 1 只需连通
        /* 尝试在 R 的诱导子图里跑一次 BFS，看能否遍历完 */
        queue<int> q;
        unordered_set<int> inR(R.begin(),R.end());
        unordered_set<int> vis;
        q.push(R[0]);  vis.insert(R[0]);

        while(!q.empty()){
            int u=q.front();q.pop();
            for(int v:G[u])
                if(inR.count(v) && !vis.count(v)){
                    vis.insert(v);
                    q.push(v);
                }
        }
        return vis.size() == R.size();
    }

    /* ---------- 拆点并建基础容量矩阵 ---------- */
    int id[MAXN];  fill(id, id + MAXN, -1);
    int n = 0;
    for (int v : R) id[v] = n++;
    int tot = 2 * n;

    vector<vector<int>> adj(tot);                  // 局部邻接表
    vector<vector<int>> base(tot, vector<int>(tot, 0));

    for (int v : R) {
        int vin = id[v] * 2, vout = vin + 1;
        base[vin][vout] = 1;                       // 顶点容量 1
        adj[vin].push_back(vout);
        adj[vout].push_back(vin);                  // 反向边
    }
    for (int u : R)
        for (int v : G[u]) if (id[v] != -1) {
            int uout = id[u] * 2 + 1, vin = id[v] * 2;
            base[uout][vin] = k;
            adj[uout].push_back(vin);
            adj[vin].push_back(uout);              // 反向边
        }

    /* ---------- 枚举所有无序点对 (u,v) ---------- */
    int sz = (int)R.size();
    for (int a = 0; a < sz; ++a)
        for (int b = a + 1; b < sz; ++b) {
            int u = R[a], v = R[b];
            auto cap = base;                       // 拷贝容量

            cap[id[u]*2][id[u]*2+1] = k;           // 源、汇容量=k
            cap[id[v]*2][id[v]*2+1] = k;

            int src = id[u]*2 + 1;                 // u_out
            int dst = id[v]*2;                     // v_in

            for (int f = 0; f < k; ++f) {          // 连找 k 条路
                vector<int> par(tot, -1);
                if (!bfs(src, dst, adj, cap, par)) return false;
                for (int x = dst; x != src; x = par[x]) {
                    int p = par[x];
                    --cap[p][x];
                    ++cap[x][p];
                }
            }
        }
    return true;
}

// 判定能否把 c 加进已知的 s‑bundle P
bool addSB(const vector<int>& P, int c, int s)
{
    vector<int> S = P; S.push_back(c);
    int k = (int)S.size() - s;
    if (k <= 1) return true;

    int id[MAXN]; fill(id, id + MAXN, -1);
    int n = 0;
    for (int v : S) id[v] = n++;
    int tot = 2 * n;

    vector<vector<int>> adj(tot);
    vector<vector<int>> base(tot, vector<int>(tot, 0));

    for (int v : S) {
        int vin = id[v]*2, vout = vin+1;
        base[vin][vout] = (v == c ? k : 1);
        adj[vin].push_back(vout);
        adj[vout].push_back(vin);
    }
    for (int u : S)
        for (int v : G[u]) if (id[v] != -1) {
            int uout = id[u]*2+1, vin = id[v]*2;
            base[uout][vin] = k;
            adj[uout].push_back(vin);
            adj[vin ].push_back(uout);
        }

    for (int i : P) {
        int src = id[i]*2, srcOut = src+1, dst = id[c]*2+1;
        auto cap = base;
        cap[src][srcOut] = k;                      // 源点容量=k

        for (int f = 0; f < k; ++f) {
            vector<int> par(tot, -1);
            if (!bfs(src, dst, adj, cap, par)) return false;
            for (int v = dst; v != src; v = par[v]) {
                int u = par[v];
                --cap[u][v];
                ++cap[v][u];
            }
        }
    }
    return true;
}

void BK_S_Bundle(vector <int> R, vector <int> P, vector <int> X, int s)
{
    if(P.empty() && X.empty())
    {
        for(int v : R) cout << v << " ";
        cout << endl;
        return;
    }

    // 遍历 P 的副本，避免修改正在遍历的容器
    vector<int> P_copy = P;
    for(int v : P_copy)
    {
        if(find(P.begin(), P.end(), v) == P.end()) continue;

        /* 1. 把 v 从 P 中删掉 (关键修正) */
        P.erase(find(P.begin(), P.end(), v));

        /* 2. 新的 R = R ∪ {v} */
        vector<int> R2 = R; R2.push_back(v);

        if(isSB(R2, s)){                    // 仍是 s‑bundle
            vector<int> P2, X2;
            for(int w : P)
                if(addSB(R2, w, s)) P2.push_back(w);
            for(int w : X)
                if(addSB(R2, w, s)) X2.push_back(w);

            BK_S_Bundle(R2, P2, X2, s);    // 递归
        }

        /* 3. 把 v 加入 X */
        X.push_back(v);
    }
}

int main()
{
    cout << "Inputing graph..." << endl;

    cin >> n >> m;
    for(int x = 1; x <= m; x++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int x = 1; x <= n; x++) sort(G[x].begin(), G[x].end());

    cout << "Graph input complete!" << endl << endl;

    //for(int x = 1; x <= n; x++) cout << x << ": " << G[x].size() << endl;
    
    vector <int> R, P, X;
    for(int x = 1; x <= n; x++) P.push_back(x);

    int s;
    cout << "Please input s: ";
    cin >> s;

    BK_S_Bundle(R, P, X, s);

    return 0;
}

测试数据

正确(?)找到了所有的maximal s-bundle

一个是这份代码的s-bunlde检验就已经错了，然后根据别人写的源码改了一下，现在正确性应该很高

第二个，改成了01递归树，有了现在这份正确性比较高的代码


#include <bits/stdc++.h>
#define MAXN 1000001
using namespace std;

int n, m, ansCnt;
vector<int> G[MAXN];
bool inR[MAXN];

/*---------------- ISAP 最大流 ----------------*/
struct Dinic {
    struct Edge { int to, rev, cap; };
    int N;
    vector<vector<Edge>> adj;
    vector<int> level, it;

    Dinic(int n = 0) { init(n); }

    void init(int n) {
        N = n;
        adj.assign(n, {});
        level.resize(n);
        it.resize(n);
    }
    void addEdge(int u, int v, int c) {          // 有向边 u→v, 容量 c
        adj[u].push_back({v, (int)adj[v].size(), c});
        adj[v].push_back({u, (int)adj[u].size() - 1, 0});
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while(!q.empty() && level[t]==-1){
            int u = q.front(); q.pop();
            for(const auto &e: adj[u])
                if(e.cap && level[e.to]==-1){
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
        }
        return level[t] != -1;
    }
    int dfs(int u, int t, int f){
        if(u == t) return f;
        for(int &i = it[u]; i < (int)adj[u].size(); ++i){
            Edge &e = adj[u][i];
            if(e.cap && level[e.to] == level[u]+1){
                int ret = dfs(e.to, t, min(f, e.cap));
                if(ret){
                    e.cap     -= ret;
                    adj[e.to][e.rev].cap += ret;
                    return ret;
                }
            }
        }
        return 0;
    }
    /* 返回 s→t 的最大流（上限 limit）*/
    int maxflow(int s, int t, int limit = INT_MAX){
        int flow = 0;
        while(flow < limit && bfs(s,t)){
            fill(it.begin(), it.end(), 0);
            int f;
            while(flow < limit && (f = dfs(s,t, limit-flow)))
                flow += f;
        }
        return flow;
    }
};

/********************************************************************
 *  判断集合 S 是否为 s-bundle
 ********************************************************************/
const int INF = 1e9;
static int vidx[MAXN];
static vector<int> touched;

/*---------- 连通性先验 ----------*/
bool isConnected(const vector<int>& S){
    if(S.empty()) return true;
    unordered_set<int> in(S.begin(), S.end());
    queue<int> q; q.push(S[0]);
    unordered_set<int> vis; vis.insert(S[0]);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v:G[u])
            if(in.count(v) && !vis.count(v)){
                vis.insert(v); q.push(v);
            }
    }
    return vis.size() == S.size();
}

/*---------- 核心判定 ----------*/
bool verifySB(const vector<int>& S, int s)
{
    int n = (int)S.size();
    if(!isConnected(S)) return false;
    if(n <= s)          return true;          // |S| ≤ s 必然满足

    int need = n - s;                         // 目标顶点割

    /* 建映射 id → 0..n-1 */
    touched.clear();
    for(int i=0;i<n;++i){ vidx[S[i]] = i; touched.push_back(S[i]); }

    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j){

            /* 只检查非相邻点对，加速 */
            if(binary_search(G[S[i]].begin(), G[S[i]].end(), S[j])) continue;

            /*---------------- 重新建网络 ----------------*/
            Dinic din(2*n);                   // vin:0..n-1, vout:n..2n-1

            for(int k=0;k<n;++k){
                /* 默认顶点容量 1 */
                din.addEdge(k, k+n, 1);
            }
            /*   u_out 和 v_out 作为源/汇 ⇒ 容量 INF   */
            din.addEdge(i, i+n, INF);
            din.addEdge(j, j+n, INF);

            for(int a=0;a<n;++a){
                int u = S[a];
                for(int v : G[u]){
                    int b = vidx[v];
                    if(b < 0) continue;           // v 不在 S
                    if(a < b){
                        din.addEdge(a+n, b, INF);
                        din.addEdge(b+n, a, INF);
                    }
                }
            }

            int s_out = i + n;
            int t_out = j + n;

            if(din.maxflow(s_out, t_out, need) < need){
                for(int v:touched) vidx[v] = -1;
                return false;
            }
        }

    for(int v:touched) vidx[v] = -1;
    return true;
}

/*---------- 单点扩展 ----------*/
bool addSB(const vector<int>& R, int c, int s)
{
    if(find(R.begin(), R.end(), c) != R.end()) return false;
    vector<int> tmp = R; tmp.push_back(c);
    return verifySB(tmp, s);
}

void outputAns(vector <int> R)
{
    for(int v:R) cout << v << ' ';
    cout << '\n';
}

void enumSB(int pos, const vector<int>& allV, vector<int>& R, int s)
{
    /*------------- 递归终点：已经考察完所有顶点 -------------*/
    if(pos == (int)allV.size())
    {
        if(R.empty()) return;             // 空集不要
        if(!verifySB(R, s)) return;       // 不是 s-bundle

        /*---- 检查极大性：再加任何剩余顶点都失败 ----*/
        for(int v : allV)
            if(find(R.begin(), R.end(), v) == R.end()){
                vector<int> tmp = R; tmp.push_back(v);
                if(verifySB(tmp, s)) return;   // 还能扩展 ⇒ 不是极大
            }

        /*---- 到这一步一定是“极大 s-bundle” ----*/
        cout << "FIND ONE: ";
        outputAns(R);
        ++ansCnt;
        return;
    }

    /*----------------------------------------------------------
     *  分支 1：不选 allV[pos]
     *---------------------------------------------------------*/
    enumSB(pos + 1, allV, R, s);

    /*----------------------------------------------------------
     *  分支 2：尝试把 allV[pos] 加进来
     *          只有“当前加入后仍然可能成为 s-bundle”才继续递归
     *---------------------------------------------------------*/
    R.push_back(allV[pos]);
    if(verifySB(R, s))
        enumSB(pos + 1, allV, R, s);      // 只有通过快速检查才深搜
    R.pop_back();                         // 回溯
}

int main()
{
    cout << "Inputing graph...\n";
    cin >> n >> m;
    for(int i=0;i<m;++i){
        int u,v; cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;++i)
        sort(G[i].begin(), G[i].end());
    cout << "Graph input complete!\n\n";

    vector<int> R;              // 当前解
    vector<int> allV;           // 顶点全集 1..n
    for(int i=1;i<=n;++i) allV.push_back(i);

    int s;
    cout << "Please input s: ";
    // cin >> s;
    s = 6;
    cout << "Here are the " << s << "-bundle(s) in this graph:\n";

    clock_t beg = clock();
    enumSB(0, allV, R, s);
    clock_t ed  = clock();

    cout << "Enumeration complete! There are "
         << ansCnt << ' ' << s << "-bundle(s) in total.\n";
    cout << "Time: " << (double)(ed-beg)/CLOCKS_PER_SEC*1000 << " ms\n";
    return 0;
}

现在这个算法呢实现起来复杂度非常高，所以在时间上是肯定不允许的，然后这个s-bundle的数量它其实也是一个指数级的东西，所以接下来具体怎么做我也还不知道

先写一个造数据的代码吧

2025.5.26
师兄说这个s-bundle还是要基于BK算法的，然后让我要仔细看一下其他近似团的极大团算法的论文，这个我确实还没看，然后还有看看最大s-bundle的那个性质能不能用在极大s-bundle枚举里面，找上界的部分可以不看。

2025.5.28
这个课题三年前就有人研究了，爆！

Listing maximal k-relaxed-vertex connected components from large graphs

K-RVCC和S-Bundle是完全一模一样的东西

Case Closed

Clique and S-Bundle