「Connected Graph」连通图

形式化题目

求顶点集为 $\{1,2,\dots,N\}$ 的无向简单连通图的个数。无向简单图指：任意两点之间至多一条边，无自环，边无方向。多组询问，每组给出一个 $N$ 。

记

G_n = \#\{\text{顶点集为}\{1,\dots,n\}\text{ 的无向简单图}\},\qquad C_n = \#\{\text{其中连通的}\}

要求对每个询问输出 $C_N$ 的精确值（不取模）。

正解

思路

朴素做法： $n$ 个标号点共有 $\binom{n}{2}$ 条可能边，枚举每条边选或不选就能生成全部 $2^{\binom n2}$ 个图，再用并查集判连通即可精确计数。

这条路的瓶颈不在判定，而在枚举方向：连通性是整体性质，删掉一条边就可能从连通变成不连通，没有任何局部判据可以先验地剪掉分支。规模稍大就数不完：

$n$	图的总数 $2^{\binom n2}$
3	8
6	32768
10	约 $3.5\times10^{13}$
50	$2^{1225}$

所以必须换个方向：不从"连通的图"出发，而从"全部的图"出发，再减掉不连通的那些。

关键观察一：容易数的是任意图，不是连通图。 每条可能边独立地"选 / 不选"，组合起来恰好不重不漏地给出所有无向简单图，因此

G_n = 2^{\binom n2}

例如 $G_1=1,\;G_2=2,\;G_3=8,\;G_4=64$ 。这是后面所有计数的全集。

关键观察二：按"1 号点所在连通块的大小"划分全集。 任取一个 $n$ 点图，看 1 号点所在的那个连通块，设它含 $k$ 个点。

一个图里 1 号点所属的连通块是唯一的，所以 $k$ 是良定义的；
$k$ 只能取 $1,2,\dots,n$ ，且每个图恰好被一个 $k$ 命中——这是划分，不会重复计数；
$k=n$ 当且仅当整个图连通。

关键观察三：固定 $k$ 后，图被切成三个互相独立的选择。（方块图只画这三个乘子；"先选出块内的另外 $k-1$ 个点"是它们之前的第四个乘子。）

text

1
2
3
4
5
6
7   第一步：选同伴 —— 从 n-1 个点里挑 k-1 个进块 ── C(n-1, k-1) 种
                          ↓
   ┌──────────────┐   ┌──────────────┐   ┌──────────────┐
   │ 块内：这 k 个 │ × │ 块与块外之间 │ × │ 块外：剩下   │
   │ 点必须连通    │   │ 一条边都没有 │   │ n-k 点边任意 │
   └──────────────┘   └──────────────┘   └──────────────┘
        C_k 种               1 种              G_(n-k) 种

选同伴：从除 1 号点外的 $n-1$ 个点中挑 $k-1$ 个作块成员，共 $\binom{n-1}{k-1}$ 种；
块内连通：这 $k$ 个点内部必须是连通图，共 $C_k$ 种；
块间无边、块外任意：块内与块外之间不能连任何边（否则 1 号点的块会变大，与"块大小为 $k$ "矛盾），而块外那 $n-k$ 个点之间的边完全自由，共 $G_{n-k}=2^{\binom{n-k}{2}}$ 种。

三个数彼此独立，直接相乘。

递推式：从全集里扣掉所有 $k<n$ （即不连通）的分类格子，剩下的正是 $k=n$ ，也就是连通图：

C_n=G_n-\sum_{k=1}^{n-1}\binom{n-1}{k-1}\,C_k\,G_{n-k},\qquad C_1=1

求 $C_n$ 只用到 $C_1,\dots,C_{n-1}$ ，按 $n$ 递增计算即可，无循环依赖。

小规模核对（ $n=4$ ， $G_4=64$ ）：

$k$ （1 号点所在块大小）	选同伴 $\binom{3}{k-1}$	块内 $C_k$	块外 $G_{4-k}$	该类图数
1	1	1	$G_3=8$	8
2	3	1	$G_2=2$	6
3	3	4	$G_1=1$	12
4（连通）	—	—	—	$64-8-6-12=38$

三行不连通类合计 $26$ ， $64-26=38$ ，与题面样例的 38 一致；前三行也正好枚举出全部不连通图。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <cstdio>
using namespace std;

typedef long long ll;

// 答案可达 2^(50*49/2) = 2^1225，约 369 位十进制，超出 64 位整数，必须自己写大整数。
// 用 10^4 进制：一段一个「万进制位」，逐段存低位在前，段与段相乘不超过 1e8，不会溢出。
const ll BASE = 10000;
const int MAXSEG = 260;

struct Big {
    int len;        // 段数，len = 0 表示数值 0
    ll seg[MAXSEG]; // 低位在前，每段小于 BASE
};

Big big_small(ll v) {
    Big r;
    r.len = 0;
    while (v > 0) {
        r.seg[r.len] = v % BASE;
        r.len++;
        v /= BASE;
    }
    return r;
}

Big big_add(Big a, Big b) {
    Big r;
    r.len = a.len > b.len ? a.len : b.len;
    ll carry = 0;
    for (int i = 0; i < r.len; i++) {
        ll v = carry;
        if (i < a.len) v += a.seg[i];
        if (i < b.len) v += b.seg[i];
        r.seg[i] = v % BASE;
        carry = v / BASE;
    }
    if (carry > 0) {
        r.seg[r.len] = carry;
        r.len++;
    }
    return r;
}

// 减法，调用者保证 a >= b（本题里被减数是「全部无向图个数」，一定不小于被扣掉的和）
Big big_sub(Big a, Big b) {
    Big r;
    r.len = a.len;
    ll borrow = 0;
    for (int i = 0; i < a.len; i++) {
        ll v = a.seg[i] - borrow;
        if (i < b.len) v -= b.seg[i];
        if (v < 0) {
            v += BASE;
            borrow = 1;
        } else {
            borrow = 0;
        }
        r.seg[i] = v;
    }
    while (r.len > 0 && r.seg[r.len - 1] == 0) r.len--;
    return r;
}

Big big_mul(Big a, Big b) {
    Big r;
    r.len = 0;
    if (a.len == 0 || b.len == 0) return r;
    ll acc[2 * MAXSEG];
    int total = a.len + b.len;
    for (int i = 0; i < total; i++) acc[i] = 0;
    for (int i = 0; i < a.len; i++)
        for (int j = 0; j < b.len; j++) acc[i + j] += a.seg[i] * b.seg[j];
    for (int i = 0; i < total; i++) { // 逐段进位，低位段处理完就再也不会变
        ll carry = acc[i] / BASE;
        acc[i] %= BASE;
        if (i + 1 < total) acc[i + 1] += carry;
    }
    r.len = total;
    while (r.len > 0 && acc[r.len - 1] == 0) r.len--;
    for (int i = 0; i < r.len; i++) r.seg[i] = acc[i];
    return r;
}

void big_print(Big a) {
    if (a.len == 0) {
        printf("0\n");
        return;
    }
    printf("%lld", a.seg[a.len - 1]);
    for (int i = a.len - 2; i >= 0; i--) printf("%04lld", a.seg[i]);
    printf("\n");
}

const int MAXN = 50;

Big graph[MAXN + 1];  // graph[n]：n 个标号点的任意无向图个数，每条可能边独立取舍，共 2^(n(n-1)/2)
Big conn[MAXN + 1];   // conn[n]：n 个标号点的连通无向图个数
ll binom[MAXN + 1][MAXN + 1]; // 组合数，最大 C(49,24) 仍在 64 位内

// n 个标号点的任意无向图个数：每条可能边独立取舍
Big graph_count(ll n) {
    ll edges = n * (n - 1) / 2;
    Big r = big_small(1);
    Big two = big_small(2);
    for (ll i = 0; i < edges; i++) r = big_mul(r, two);
    return r;
}

int main() {
    for (int i = 0; i <= MAXN; i++) { // 杨辉三角求组合数
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++)
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
    }
    graph[0] = big_small(1);
    for (int n = 1; n <= MAXN; n++) graph[n] = graph_count(n);

    // conn[n] = 全部无向图个数 - 1 号点所在连通块大小 k < n 的分类情形：
    // 选 k-1 个同伴 C(n-1,k-1)，块内连通 conn[k]，块外任意 graph[n-k]
    for (int n = 1; n <= MAXN; n++) {
        Big sum = big_small(0);
        for (int k = 1; k < n; k++) {
            Big term = big_mul(big_small(binom[n - 1][k - 1]), conn[k]);
            term = big_mul(term, graph[n - k]);
            sum = big_add(sum, term);
        }
        conn[n] = big_sub(graph[n], sum);
    }

    ll n;
    // 输入多组，0 表示输入终止（0 本身不产生输出行）
    while (scanf("%lld", &n) == 1) {
        if (n == 0) break;
        big_print(conn[n]);
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 21:46
# update_at: 2026-10-01 21:50

import sys
from functools import cache
from math import comb

TERMINATOR = 0  # 输入以单独一行的 0 结束，它不是一次询问


def graph_count(n: int) -> int:
    """n 个标号点的任意无向图个数：每条可能边独立取舍，共 2^(n(n-1)/2) 个。"""
    return 1 << (n * (n - 1) // 2)


@cache
def connected_count(n: int) -> int:  # n 最大 50，缓存让多组询问与递归都不重复计算
    """n 个标号点的连通无向图个数：全集减去 1 号点所在块大小 k<n 的全部分类情形。"""
    return graph_count(n) - sum(
        comb(n - 1, k - 1) * connected_count(k) * graph_count(n - k)  # 选 k-1 个同伴，块内连通，块外任意
        for k in range(1, n)
    )


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    asked = [n for n in data if n != TERMINATOR]  # 丢弃终止用的 0

    lines = '\n'.join(map(str, map(connected_count, asked)))
    if lines:  # 只有终止标记 0 时一行都不输出，而不是打印一个空行
        print(lines)


if __name__ == "__main__":
    solve()

复杂度

时间：记忆化后共 $\sum_{n=1}^{N}(n-1)=O(N^2)$ 次大整数乘加运算， $N=50$ 时约 1225 次、操作数不到 370 位十进制，毫秒级。
空间：缓存 $O(N)$ 个大整数，可忽略。
对比朴素枚举的 $O\!\left(2^{\binom n2}\alpha(n)\right)$ ，差距是天壤之别。
与代码对应：graph_count(n) 就是 $G_n$ ，connected_count(n) 是带 @cache 的 $C_n$ 递推，求和里的三项乘以 $\binom{n-1}{k-1}$ 、 $C_k$ 、 $G_{n-k}$ 一一对应；solve 只负责剔掉终止标记 0 并逐行输出。

总结

计数题的通用思路是：当一个性质整体性强、难以正向枚举时，先数"全集"，再把全集按某个唯一可识别的量分类，用"全集 − 非目标类"得到答案。本题选 1 号点的连通块大小作分类量，因为它是每个图唯一确定、且恰好把"连通"对应到 $k=n$ 的分类。写代码时只需注意两点：块内与块外之间必须无边（这一条最容易写反），以及 $N=50$ 时答案约 369 位十进制，必须用 Python 原生大整数而不是 64 位整型。

「Connected Graph」 连通图

目录

形式化题目

正解

思路

代码

复杂度

总结

「Connected Graph」连通图