cjw-wjc-qwq 的福瑞王国
图论 / 环计数 作者:CJW 更新于 2026-11-09 环计数状压DP子集枚举图论

简单环计数(状压 DP)

统计无向图里长度 ≥3 的简单环个数。dp[S][i] + 固定最小值起点 + lowbit 判环,O(2^n·(n+m)),附子集遍历等小知识点


问题(CF 11D):给一张无向简单图,统计简单环(长度 ≥ 3,环上点在环内互不相同,允许有弦)的个数。

n ≤ 19 → 状压 DP。

代码(CF 11D 已 AC)

#include <bits/stdc++.h>
using namespace std;
#define int long long
static const long long MOD = 998244353;
const int N = 19;
vector<int> g[N];
int n,m;
int dp[1<<N][N+1];

void sol() {
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i=1;i<=n;i++) dp[1<<(i-1)][i]=1;
    int ans=0;
    for(int s=0;s<(1<<n);s++){
        for(int i=1;i<=n;i++){
            if(!dp[s][i]) continue;
            for(auto v:g[i]){
                if((s&-s)>(1<<(v-1))) continue;
                if(s&(1<<(v-1))){
                    if((s&-s)==(1<<(v-1))) ans+=dp[s][i];
                }else{
                    dp[s|(1<<(v-1))][v]+=dp[s][i];
                }
            }
        } 
    }
    cout<<(ans-m)/2<<endl;
}

signed main(){
    int T=1;
    //cin>>T;
    while(T--){
        sol();
    }
    return 0;
}

状态设计

dp[S][i] = 以 S 中编号最小的点为起点、当前停在 i、已经访问过 S 中所有点的路径条数。

  • 起点固定为 S 的最低位 → lowbit(S) = S & -S,它对应 1 << (起点-1);
  • 初始化:每个单点集 dp[1<<(i-1)][i] = 1(只有自己);
  • 转移(枚举 i 的邻点 v):
情况处理原因
v ∉ Sdp[S∪{v}][v] += dp[S][i]继续往外走
v ∈ S 且 v 就是起点ans += dp[S][i]回到起点 → 形成一个环
v ∈ S 但不是起点跳过否则同一个环会被重复统计多次

关键约束:if((s&-s) > (1<<(v-1))) continue; 只允许走向编号不小于起点的点。这样每个环只会在它的最小编号点处被统计一次,不会因为起点不同而重复。

最后一步 (ans - m) / 2:

  • 长度 2 的”往返” start → v → start 被当成环数了,恰好每条边一次 → 减 m;
  • 每个长度 ≥3 的环会被两个方向各数一次 → 除以 2。

小知识点

1. 子集遍历的四种写法

// ① 遍历所有子集
for(int s = 0; s < (1 << n); s++) { }

// ② 遍历 s 的所有「非空子集」(含 s 本身)
for(int t = s; t; t = (t - 1) & s) { }

// ③ 遍历 s 的所有「真子集」(不含 s 本身,也不含空集)
for(int t = (s - 1) & s; t; t = (t - 1) & s) { }

// ④ 遍历 s 的所有「超集」
for(int t = s; t < (1 << n); t = (t + 1) | s) { }
  • 写法 ②③ 的核心是 (t - 1) & s:从 t 里去掉最低的 1 之后,再和 s 取交,得到下一个更小的子集;
  • 把「枚举所有 s」和「枚举 s 的子集」套起来,总复杂度是 O(3^n)(每个点有三种状态:不在 s / 在 s 不在 t / 在 t)——斯坦纳树、集合划分 DP 都靠这个。

2. lowbit 家族

int lowbit = s & -s;              // 最低位的 1(本题就是"起点"对应的位)
int rest   = s & (s - 1);         // 去掉最低位的 1
int pos    = __builtin_ctz(s);    // 最低位的下标(0 开始,等价于 log2(lowbit))
int cnt    = __builtin_popcount(s);   // 集合大小

本题用 s & -s 既当「起点是谁」,又当「v 是不是起点」的比较对象:

if((s&-s) > (1<<(v-1))) continue;        // v 编号比起点小 → 不走
if((s&-s) == (1<<(v-1))) ans += dp[s][i]; // v 就是起点 → 成环

3. 为什么 for (s = 0; s < (1<<n); s++) 递增就够

转移只从 s 走到 s | (1<<(v-1)),而任何 s | bit > s(加了位只会变大),所以按 s 从小到大枚举时,用到的状态一定已经算完——天然拓扑序,不需要按 popcount 分层。

4. 判断 / 修改某一位

bool in   = s >> (v - 1) & 1;     // 或写成 s & (1 << (v - 1))
int  add  = s | (1 << (v - 1));   // 加进来
int  del  = s & ~(1 << (v - 1));  // 删掉

5. 坐标习惯要统一

代码里点编号是 1 到 n,位是 0 到 n-1,所以永远是 1 << (v - 1)。 写混(比如某处写 1 << v)会静默出错、且很难查——这是本题最常见的翻车点。

复杂度

复杂度说明
时间O(2^n · (n + m))每个状态枚举 i 和 i 的邻边
空间O(2^n · n)dp[1<<19][20],long long 约 84MB(CF 11D 内存 256MB 够用)

空间优化:若内存吃紧,把 dp 换成 32 位 int(约 42MB);答案不超过 19!/2 ≈ 6e16,long long 存答案够用。

易错点 / 易混点

问题错误后果正确做法
起点不固定同一个环被数很多次,答案爆炸用 s & -s 固定为最小点
v ∈ S 但非起点时也累加重复计数只在 v == 起点 时累加
忘了 (ans - m) / 2多算长度 2 的往返、且每个环算两次先减 m 再除 2
1 << (v-1) 写成 1 << v位与点错位,答案随机点 1..n 对应位 0..n-1
有重边时不去重同一条边被当多条路径,环数虚高本题保证简单图;否则先对邻接表去重
dp 用 long long 又内存紧张MLE状态数组用 int,答案单独用 long long
n < 3无输出/负数特判或让公式自然给 0(ans=0 时 (0-m)/2 需注意 m 也要为 0)

同类题

  • CF 11D A Simple Task — 本题
  • 统计三角形个数:n ≤ 2e5 的图上用「按度数分类 / bitset」做,不是这个状压套路
  • 统计环的个数(含重边、模数):状态按 popcount 分层 + 组合数,n 很大时通常是计数组合题

延伸

  • 状压 DP 的三件套:位运算判集合、lowbit 找代表元、子集枚举做合并;
  • 图上状压(本题)与集合状压(如 dp[mask] 表示选了哪些点/物品)是两种不同套路,别混用;
  • 若题目要求输出每个环而不是个数,状压就不够了,要用「删点后的生成环 / DFS 枚举规范环」。