环上计数

GitHub跳转原题关系图返回列表

Tarjan 边栈求点双:桥即不在任何简单环上的边;块内边数大于点数时块内每条边都在至少两个简单环上,累加这些块的边数。

OJ: roj

题目 ID: 1735

难度:提高

标签:图论点双连通分量Tarjanpython

创建: 2026-10-07 20:26

更新: 2026-10-07 20:26

形式化题目

给定无向图 G=(V,E)G = (V, E)(∣V∣=n|V| = n,∣E∣=m|E| = m),无重边、无自环,不保证连通。求两个计数:

a1=#{e∈E:e 不在 G 的任何一条简单环上},a2=#{e∈E:e 至少在 G 的两条不同的简单环上}.a_1 = \#\{e \in E : e \text{ 不在 } G \text{ 的任何一条简单环上}\}, \qquad a_2 = \#\{e \in E : e \text{ 至少在 } G \text{ 的两条不同的简单环上}\}.

这里的"简单环"指顶点不重复、边长 ⩾3\geqslant 3 的回路,且回路必须整条由 GG 的顶点和边组成(不能重编号顶点,也不能把不存在的边当作环上边)。于是每条边上的环数只由图的结构决定。

所求的两个量彼此不重叠:环数为 00 的边计进 a1a_1,环数 ⩾2\geqslant 2 的边计进 a2a_2,环数恰为 11 的边两个都不计,所以 a1+a2⩽ma_1 + a_2 \leqslant m。

正解

思路

两个答案看起来要分别回答"零个环"和"两个以上环",但可以用同一件工具一次算完:Tarjan 的点双连通分量(块)分解。

答案一:ee 不在任何简单环上   ⟺  \iff ee 是桥。

若 e=(u,v)e = (u, v) 是割边,删掉它 u,vu, v 就断开,任何回路都过不来,自然没有简单环含 ee。反过来,ee 不是桥时,删掉 ee 后 uu 仍能到达 vv,取一条 u→vu \to v 的路径,其内部顶点必与 ee 的两个端点互不相同(如果路径中途经过 uu 或 vv,把路径截短即可),于是这条路径加上 ee 就是一个只用到 ee 一次的简单环。所以 a1a_1 就是桥数,Tarjan 里用 low[v] > dfn[u] 逐条数即可。

答案二:逐个点双检查"边数是否大于点数"。

块的分解把一个连通块切成一棵"块-割点树",每个块是极大的 2-连通子图(或一条桥)。关键性质是:

  1. 同一个块内的任意两条边同属于某个简单环。 这是 2-连通图的经典结论(等价说法是"过任意两条边都有简单回路",可由耳分解或 Menger 定理推出):在 2-连通图里对任意两条边各取一个端点,两个端点之间都有两条内部不相交的道路,拼起来就是过一个端点所在边与另一条边的简单环。

  2. 设块 BB 有 nBn_B 个顶点、mBm_B 条边。单条桥的块满足 nB=2,mB=1n_B = 2, m_B = 1;nB⩾3n_B \geqslant 3 的块是 2-连通的,度数之和 2mB=∑vdeg⁡v⩾2nB2m_B = \sum_v \deg v \geqslant 2n_B 给出 mB⩾nBm_B \geqslant n_B。于是非桥的块只有两种情形:

    • mB=nBm_B = n_B:由 2mB=2nB2m_B = 2n_B 得每点度数恰为 22,BB 就是一个简单环,此时任何简单环都必须用上全部 nBn_B 条边(每个点度数已用尽),故块内每条边恰在 1 个简单环上;
    • mB>nBm_B > n_B:反设某条边 ee 只在一个简单环 CC 上。因为 mB>nB=∣E(C)∣m_B > n_B = |E(C)|(CC 是块内的环,长度不超过 nBn_B),块内必有边 h∉Ch \notin C。由性质 1,存在同时包含 ee 与 hh 的简单环 C′C';h∉Ch \notin C 迫使 C′≠CC' \neq C,于是 ee 落在两个不同简单环上,矛盾。所以每条边至少在两个简单环上。

    换句话说,mB>nBm_B > n_B 意味着这个块"环太多",块内每条边都进 a2a_2。

    小例子:nn 个点的环本身只有一条简单环可走,每条边恰在 1 个环上;一旦加一条弦(mB=nB+1m_B = n_B + 1),每条边立刻多出第二条环。例如四边形 0-1-2-3-0 加上弦 (0,2)(0,2) 后,边 (0,1)(0,1) 既在 0-1-2-0 上,也在 0-1-2-3-0 上。

于是算法的形状就定下来了:跑一遍 Tarjan,同时完成两件事——用 low[v] > dfn[u] 数桥得到 a1a_1;用边栈弹出每个块,统计块内边数 mBm_B 与去重后的点数 nBn_B,把 mB>nBm_B > n_B 的 mBm_B 累加得到 a2a_2。

块内点数为什么必须去重? 边栈弹出的是块内边,同一条边的两个端点会多次出现(nBn_B 个点、mBm_B 条边一共 2mB2m_B 个端点),所以不能用出现次数当点数。做法是用时间戳标记:每进入一个新块就把块号加一,见到某点的时间戳不等于当前块号才计数并打标记,这样每个点只贡献一次,且标记是整数比较,不用 std::set(原题内存只有 32MB 时这点很关键)。

实现细节。 nn 可达 10410^4 且数据里可能有长链(本目录的生成器就专门造了 n=104n = 10^4 的深链树),递归 Tarjan 有爆栈风险,因此用显式栈迭代:每层显式压入 (顶点, 出边游标, 入边编号),弹出时才算这一层的收尾。边的存储把无向边 ii 拆成两条弧(C++ 用 2i / 2i+1,Python 同样用 2i / 2i+1),于是 e⊕1e \oplus 1 恒为反向弧,"跳过父边"只需比较 e=fe⊕1e = \text{fe} \oplus 1,不必另存每条弧的起点,也不怕重边。根的 fe\text{fe} 要选一个与所有合法弧号都不同的哨兵:C++ 里弧号从 22 起,用 0;Python 里弧号从 00 起,用 -1(因为 -1 ^ 1 = -2 也不是合法弧号)。

块的弹出时机是固定的:uu 从栈里弹出、回到父亲 pp 时,若 low[u] >= dfn[p],就说明 pp 的分割点身份成立、以父边 fe\text{fe} 结尾的这个块已经完整,从边栈里一路弹到 fe\text{fe} 为止。这一次弹出同时决定了两件事——fe\text{fe} 是不是桥(low[u] > dfn[p])、这个块的 mBm_B 与 nBn_B 谁大。

代码

python
#!/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-07 20:26
# update_at: 2026-10-07 20:26

import sys

# 边弧编号约定:无向边 i 拆成弧 2i(u->v)与 2i+1(v->u),于是 e ^ 1 恒为反向弧,
# 「跳过父边」只要比较 e == (fe ^ 1);根的 fe 用 -1,因为 -1 ^ 1 = -2 不是合法弧号。
type Adj = list[list[int]]  # adj[u] = 从 u 出发的弧编号列表


def count_edges(n: int, adj: Adj, arc_to: list[int]) -> tuple[int, int]:
    """Tarjan 点双;返回 (桥数, 落在「边数 > 点数」块内的边数)。

    桥 = 不在任何简单环上的边(low[u] > dfn[父]);块内边数 > 点数时块必含
    >= 2 个环且每条边都至少属于两个简单环,把这些块的边数累加即为第二个答案。
    """
    dfn = [0] * n
    low = [0] * n
    vmark = [0] * n     # 统计块内点数的去重标记:值等于当前块号表示本块内已数过
    estack: list[int] = []  # 边栈:每弹空一次得到一个点双
    fu = [0] * n        # 迭代 dfs 的帧:当前点
    fptr = [0] * n      # 帧内游标:已处理到邻接表第几条弧
    ffe = [-1] * n      # 帧的入边编号,-1 表示该帧是根(无父边)
    ans1 = ans2 = 0
    timer = 0
    blk = 0

    for s in range(n):
        if dfn[s]:
            continue
        timer += 1
        dfn[s] = low[s] = timer
        top = 0
        fu[0], fptr[0], ffe[0] = s, 0, -1
        while top >= 0:                      # 显式栈 dfs:深链可达 1e4,不用递归
            u = fu[top]
            arcs = adj[u]
            pos = fptr[top]
            if pos < len(arcs):
                fptr[top] = pos + 1
                e = arcs[pos]
                is_parent_arc = e == (ffe[top] ^ 1)  # 用弧号判父边:反向弧恒为 e ^ 1
                if is_parent_arc:
                    continue
                v = arc_to[e]
                if dfn[v] == 0:              # 树边:入栈后进入 v
                    estack.append(e)
                    timer += 1
                    dfn[v] = low[v] = timer
                    top += 1
                    fu[top], fptr[top], ffe[top] = v, 0, e
                elif dfn[v] < dfn[u]:        # 回边:只从较深的一端入栈一次
                    estack.append(e)
                    if dfn[v] < low[u]:
                        low[u] = dfn[v]
            else:
                fe = ffe[top]
                top -= 1                     # u 的邻接表走完,弹出 u
                if fe < 0:                   # 根:它的块已由子节点返回时全部弹空
                    continue
                parent = fu[top]
                if low[u] < low[parent]:
                    low[parent] = low[u]
                if low[u] >= dfn[parent]:    # 找到一个点双,它含父边 fe
                    if low[u] > dfn[parent]:
                        ans1 += 1            # 父边是桥
                    blk += 1
                    ecnt = vcnt = 0
                    while True:
                        e = estack.pop()
                        ecnt += 1
                        a, b = arc_to[e ^ 1], arc_to[e]  # e 的起点、终点
                        if vmark[a] != blk:
                            vmark[a] = blk
                            vcnt += 1
                        if vmark[b] != blk:
                            vmark[b] = blk
                            vcnt += 1
                        if e == fe:
                            break
                    if ecnt > vcnt:
                        ans2 += ecnt
    return ans1, ans2


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    while True:
        n, m = next(data), next(data)
        if n == 0 and m == 0:                # 输入结束
            break
        arc_to = [0] * (2 * m)
        adj: Adj = [[] for _ in range(n)]
        for i in range(m):
            u, v = next(data), next(data)
            arc_to[2 * i], arc_to[2 * i + 1] = v, u
            adj[u].append(2 * i)
            adj[v].append(2 * i + 1)
        ans1, ans2 = count_edges(n, adj, arc_to)
        out.append(f"{ans1} {ans2}")
    print("\n".join(out))


if __name__ == "__main__":
    solve()
cpp
/**
 * 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-07 20:26
 * update_at: 2026-10-07 20:26
 */

// 环上计数:多组数据,每组求
//   ans1 = 不在任何简单环上的边数(= 桥数)
//   ans2 = 在至少两个简单环上的边数(= 「边数 > 点数」的点双连通分量里的边数之和)
// 读到 0 0 结束。n <= 1e4,m <= 1e5,点从 0 开始编号。

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

const int MAXN = 10005;   // 点数上限 1e4,留一点余量
const int MAXM = 200005;  // 无向边存成两条有向边:2 * 1e5

typedef long long ll;

// 链式前向星。边从 2 开始编号,于是 e 与 e ^ 1 互为反向边,
// 「跳过父边」只要比较 e == (fe ^ 1),不用额外存每条边的起点。
int head[MAXN];   // head[u]:点 u 的第一条出边
int eto[MAXM];    // eto[e]:边 e 的终点
int enxt[MAXM];   // enxt[e]:与 e 同起点的下一条边
int edge_cnt;

int dfn[MAXN];     // dfn[u]:u 的 dfs 序,0 表示未访问
int low[MAXN];     // low[u]:u 的子树能通过回边到达的最小 dfn
int vstamp[MAXN];  // 统计块内点数用的时间戳:等于当前块号表示本块内已数过
int estack[MAXM];  // 边栈:每次弹栈结束就得到一个点双(块)
int estop;

ll ans1, ans2;  // 一组数据的两个答案

// 迭代 dfs 的一帧。深链可长达 1e4,递归写法有爆栈风险,故用显式栈。
struct Frame {
    int u;   // 当前点
    int it;  // 正在处理的出边编号,0 表示邻接表已走完
    int fe;  // 进入 u 的树边编号,0 表示 u 是本次 dfs 的根
};
Frame fstk[MAXN];

// 读入一组数据:n 个点、m 条边,并重置本组用到的全局数组
void read_graph(int n, int m) {
    edge_cnt = 2;  // 边编号从 2 开始,0 和 1 留给「空边」
    for (int i = 0; i < n; i++) {
        head[i] = 0;
        dfn[i] = 0;
        low[i] = 0;
        vstamp[i] = 0;  // 块号从 1 开始,0 天然表示「还没在块里出现过」
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        eto[edge_cnt] = v;
        enxt[edge_cnt] = head[u];
        head[u] = edge_cnt++;
        eto[edge_cnt] = u;
        enxt[edge_cnt] = head[v];
        head[v] = edge_cnt++;
    }
}

// 弹边栈直到弹出入边 pe,得到一个点双。返回块内边数,点数由调用方用块号去重统计。
// 块内边数与点数决定了这个块的性质:边数 > 点数时块内每条边都在至少两个简单环上。
int pop_block(int pe, int blk_id) {
    int ecnt = 0;
    int vcnt = 0;
    while (true) {
        int e = estack[estop--];
        ecnt++;
        int a = eto[e ^ 1];  // 边 e 的起点 = 反向边的终点
        int b = eto[e];      // 边 e 的终点
        if (vstamp[a] != blk_id) {
            vstamp[a] = blk_id;
            vcnt++;
        }
        if (vstamp[b] != blk_id) {
            vstamp[b] = blk_id;
            vcnt++;
        }
        if (e == pe) break;  // 回到入边,本块弹完
    }
    return ecnt > vcnt ? ecnt : 0;  // 边数 <= 点数时该块不贡献 ans2
}

// 从点 s 出发迭代 dfs,求以它所在连通块里所有点双
void dfs_from(int s, int &timer, int &blk_id) {
    dfn[s] = low[s] = ++timer;
    int top = 0;
    fstk[0].u = s;
    fstk[0].it = head[s];
    fstk[0].fe = 0;

    while (top >= 0) {
        int u = fstk[top].u;
        int it = fstk[top].it;
        if (it != 0) {
            fstk[top].it = enxt[it];  // 先推进游标,后面可以自由访问栈
            if (it == (fstk[top].fe ^ 1)) continue;  // 是父边的反向边,跳过
            int v = eto[it];
            if (dfn[v] == 0) {
                estack[++estop] = it;  // 树边入栈
                dfn[v] = low[v] = ++timer;
                top++;
                fstk[top].u = v;
                fstk[top].it = head[v];
                fstk[top].fe = it;
            } else if (dfn[v] < dfn[u]) {
                estack[++estop] = it;  // 回边:只从较深的一端入栈一次
                low[u] = min(low[u], dfn[v]);
            }
        } else {
            int fe = fstk[top].fe;
            top--;  // 弹出 u
            if (fe == 0) continue;  // 根节点,其块已在子节点返回时全部弹完
            int p = fstk[top].u;
            low[p] = min(low[p], low[u]);
            if (low[u] >= dfn[p]) {
                if (low[u] > dfn[p]) ans1++;  // 割边:不在任何简单环上
                blk_id++;
                ans2 += pop_block(fe, blk_id);
            }
        }
    }
}

// 处理一组数据并输出一行答案
void solve_group(int n, int m) {
    read_graph(n, m);

    ans1 = 0;
    ans2 = 0;
    estop = 0;
    int timer = 0;
    int blk_id = 0;

    // 孤立点不构成块,但它的 head 为 0,dfs 进来也只会立刻弹出,无需特判
    for (int s = 0; s < n; s++) {
        if (dfn[s] == 0) dfs_from(s, timer, blk_id);
    }
    cout << ans1 << ' ' << ans2 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;  // 结束标志
        solve_group(n, m);
    }
    return 0;
}

复杂度

每组数据时间 O(n+m)O(n + m)(Tarjan 遍历每条弧一次,边栈总分摊 O(m)O(m)),空间 O(n+m)O(n + m)。题面上限 n=104n = 10^4、m=105m = 10^5,C++ 实测最大测例组(n=104n = 10^4、m=105m = 10^5 随机)在 0.020.02 s 量级,多组满规模也远低于 1 s。Python 版同样只有一次迭代 DFS,纯标准库无第三方依赖。

总结

本题的落点是"边的环计数"与"块结构"之间的对应关系:

边所在的简单环数 图结构判据 计入
0 桥(low[v] > dfn[u]) a1a_1
1 所在的块满足 mB=nBm_B = n_B(块就是一个简单环) 不计
⩾2\geqslant 2 所在的块满足 mB>nBm_B > n_B a2a_2,按块内边数整块累加

三个量互相补充:一个块要么是桥(mB=nB−1m_B = n_B - 1,块内只有一条边,环数全为 00),要么是纯环(mB=nBm_B = n_B,环数全为 11),否则 mB>nBm_B > n_B(环数全 ⩾2\geqslant 2)。所以 a1a_1 与 a2a_2 可以一次 Tarjan 同时得到,不需要真的把每个环枚举出来(环的数量可能是指数级)。

容易写错的三个点:一是块内点数必须去重(用块号时间戳最省内存,不必开 set);二是跳过父边要用弧编号异或而不是"顶点等于父点"(前者在带重边的一般图上同样正确,而且实现更简单);三是深层图要用迭代栈而不是递归。

备注

素材源 new_ROJ/problems/1735/ 里带有数据生成脚本(data.py)与标程(std.cpp),说明本目录的 data/ 是自造的,题面也可能来自网络重建,出题意图与官方原题可能有偏差。经实跑核对,标程算法与上面的推导一致(边栈点双 + 边数大于点数的块累加),本目录的 C++ 与 Python 解法在全部 10 个测试点上输出与 data/*.out 逐字节一致;另用枚举全部简单环的暴力解在 n⩽9n \leqslant 9 的 554 组随机/结构图上与本题解逐组对拍一致。但 data/ 不含官方数据,不能等同于官方 AC。