度数不超过 3 时点对最大流只可能是 0/1/2/3,用并查集、边双连通分量与「删每条边后的边双划分」三层等价类分别数出流量至少 1/2/3 的点对数。
OJ: roj
题目 ID: 1731
难度:提高+/省选-
标签:图论边双连通分量最大流最小割并查集python
创建: 2026-10-07 20:29
更新: 2026-10-07 20:29
形式化题目
给定一张
数据范围:
样例 1:
正解
思路
朴素做法的规模。 直接对每一对点跑一次最大流:点对数是
关键观察一:流量只可能是
所以
问题从"求每对点的流量"变成了"对
关键观察二:三层判定分别对应三种连通性。
:等价于 在原图中连通。 沿任一条路径推 单位流; 不连通则割集为空、流量 。→ 用并查集数连通分量内的点对数。 :等价于 属于同一边双连通分量( -边连通)。 两条边不相交路径正是 -边连通的定义(Menger 定理);反过来若存在桥把两点分开, 割集只有那一条边,流量至多 。→ 求出所有桥,忽略桥做 flood-fill,数同一块内的点对数。 :等价于删掉任意一条边后 仍在该图的同一边双连通分量里。 一方面 条边不相交路径删掉一条还剩 条;另一方面只要某条边 一删就把 分开, 则 与另一条分开 的割边构成大小 的割,流量至多 。这就是本层的判据。
前两层各扫一遍图即可,第三层看起来需要"对每条边删一次再求边双",也就是
第三层怎么落地:等价类精化。 设
其中把二元组按字典序排序后重编号,编号相同当且仅当二元组相同。
这样的"精化"只有分裂没有合并,
几个可以省掉的工作量:
- 桥不必检验。 删掉一条桥只会让划分变细(桥本来就不在任何非平凡边双块内),
不会把原本同块的边双划分拆开,所以只对满足
的非桥边跑循环。 - 类数达到
就收工。 全是单点时再细分也只能保持单点,此时每个类只有 个点、 点对数为 ,可以直接 break。 - 重编号用确定性手段,不用哈希。 Python 版把二元组压成
cls[v]*(n+1)+bel[v]当作dict的键(键互不相同,不存在冲突);C++ 版更进一步,用两趟计数排序 (先按bel稳定排序、再按cls稳定排序)把每轮压到,连排序的 因子和哈希表开销都省了。两边的划分结果完全一致。
一个容易踩的边界:
代码
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:29
# update_at: 2026-10-07 20:29
import sys
NO_BAN = -1 # 求「原图」时的 ban 取值:一条边都不删
ALL_EDGES = None # 传给 flood 的 skip 参数:没有任何边被标成桥(全部边都保留)
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Csr = tuple[list[int], list[int], list[int], list[int]] # CSR:区间起点 / 邻点 / 邻边号 / 度数
type EdgeList = list[tuple[int, int]] # 原始边表,下标就是边编号
type ClassCount = dict[int, int] # 等价类号 -> 该类里的点数
type ClassRank = dict[int, int] # (上一轮类号, 本轮分量号) 编成的复合键 -> 新类号
def build_csr(n: int, m: int, edges: EdgeList) -> Csr:
"""把边表压成 CSR:点 v 的邻边占下标区间 [start[v], start[v]+deg[v]),无向边登记两次。
邻边存两份信息:另一端点 adj_v、原始边号 adj_e(判桥、删边都要按边号来)。
"""
deg = [0] * (n + 2)
for u, v in edges:
deg[u] += 1
deg[v] += 1
start = [0] * (n + 2)
total = 0
for v in range(1, n + 1):
start[v] = total
total += deg[v]
start[n + 1] = total
adj_v = [0] * (2 * m)
adj_e = [0] * (2 * m)
pos = start[:] # 写入游标,初值就是每个点区间的起点
for e, (u, v) in enumerate(edges):
adj_v[pos[u]], adj_e[pos[u]] = v, e
pos[u] += 1
adj_v[pos[v]], adj_e[pos[v]] = u, e
pos[v] += 1
return start, adj_v, adj_e, deg
def flood(csr: Csr, n: int, ban: int, skip: bytearray | None) -> list[int]:
"""忽略 skip 中标 1 的边与被删边 ban,用 flood-fill 给连通块编号。
skip 为空时得到的就是普通连通分量编号(flow >= 1 的判据);
skip 是桥标记时,剩下的每个连通块就是一个边双连通分量(flow >= 2 的判据)。
"""
start, adj_v, adj_e, deg = csr
label = [0] * (n + 1)
comp = 0
for s in range(1, n + 1):
if label[s]:
continue
comp += 1
label[s] = comp
st = [s]
while st:
u = st.pop()
for i in range(start[u], start[u] + deg[u]):
e = adj_e[i]
removed = e == ban or (skip is not ALL_EDGES and skip[e]) # 被删边或桥
if removed:
continue
w = adj_v[i]
if not label[w]:
label[w] = comp
st.append(w)
return label
def two_ecc(csr: Csr, n: int, m: int, ban: int) -> list[int]:
"""删掉边 ban 后每个点所属的边双连通分量编号(ban = NO_BAN 表示不删边)。
先迭代式 Tarjan 标出所有桥,再忽略桥与被删边 flood-fill,每块就是一个分量。
写成迭代是为了躲开 Python 的递归深度限制——n = 3000 的链足以撑爆默认递归栈。
"""
start, adj_v, adj_e, deg = csr
dfn = [0] * (n + 1) # Tarjan 时间戳,0 表示还没访问
low = [0] * (n + 1) # 追溯值:子树里能绕回的最早时间戳
par = [-1] * (n + 1) # 每个点是从父亲哪条边下来的,用来排除"原路返回"
cur = start[:] # 邻边游标:每个点已经扫到区间里的哪一个位置
is_bridge = bytearray(m)
vstk = [0] * (n + 1) # DFS 顶点栈
estk = [0] * (n + 1) # 与顶点栈同高的入边栈:estk[top] 是 vstk[top] 的入边
timer = 0
for s in range(1, n + 1): # 图可以不连通,逐分量起一次 DFS
if dfn[s]:
continue
timer += 1
dfn[s] = low[s] = timer
vstk[0] = s
estk[0] = -1
top = 1
while top:
u = vstk[top - 1]
i = cur[u]
end = start[u] + deg[u] # u 每轮都变,区间右端也要跟着重算
while i < end and adj_e[i] == ban: # 被删的边直接跳过
i += 1
cur[u] = i
if i >= end: # 回溯:u 的子树处理完毕,可以判桥了
top -= 1
if top:
p = vstk[top - 1]
if low[u] > dfn[p]:
is_bridge[estk[top]] = 1 # 树边 (p,u) 是桥
if low[u] < low[p]:
low[p] = low[u]
continue
cur[u] = i + 1
e = adj_e[i]
w = adj_v[i]
if not dfn[w]: # 树边:压栈,等回溯时判桥
timer += 1
dfn[w] = low[w] = timer
par[w] = e
vstk[top] = w
estk[top] = e
top += 1
continue
is_back_edge = e != par[u] and dfn[w] < low[u] # 回边,且指向祖先
if is_back_edge:
low[u] = dfn[w]
return flood(csr, n, ban, is_bridge)
def count_pairs(label: list[int]) -> int:
"""同一等价类内部的点对数之和,即 #{(i<j) : label[i] == label[j]}。
label 的下标 0 是占位格(本题不用点 0),只统计 label[1..n],
否则占位格会被并进类号 0 的那一类,凭空多算出若干点对。
"""
cnt: ClassCount = {}
for x in label[1:]:
cnt[x] = cnt.get(x, 0) + 1
return sum(c * (c - 1) // 2 for c in cnt.values())
def count_flow3_pairs(csr: Csr, n: int, m: int, edges: EdgeList, bel0: list[int]) -> int:
"""flow >= 3 的点对数:删掉任意一条边后两点仍同属一个边双分量。
删「桥」不会改变原图的边双划分(删边只会让划分变细、不可能合并,而桥不在任何
非平凡块内部),所以只检验非桥边。每轮按 (上一轮类号, 本轮分量号) 把等价类细分
一次——这类精化只分裂、不合并,跑完所有非桥边后同类的点对恰好就是 flow >= 3。
没有非桥边就意味着原图是森林(每条边都是桥),删一条边必然切断,cnt3 = 0。
"""
non_bridge = [e for e, (u, v) in enumerate(edges) if bel0[u] == bel0[v]]
if not non_bridge:
return 0
cls = [0] * (n + 1) # 初值全相同,是最粗的起点
for ban in non_bridge:
bel = two_ecc(csr, n, m, ban)
rank: ClassRank = {}
for v in range(1, n + 1):
key = cls[v] * (n + 1) + bel[v] # 拼成一个可哈希的二元组键
if key not in rank:
rank[key] = len(rank)
cls[v] = rank[key]
if len(rank) == n: # 类已经全是单点,再细分也不会变回来(此时 cnt3 必为 0)
break
return count_pairs(cls)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
edges: EdgeList = [(next(data), next(data)) for _ in range(m)]
csr = build_csr(n, m, edges)
bel0 = two_ecc(csr, n, m, NO_BAN) # 原图的边双划分,后两层都要用
cnt1 = count_pairs(flood(csr, n, NO_BAN, ALL_EDGES)) # 连通 = flow >= 1
cnt2 = count_pairs(bel0) # 2-边连通 = flow >= 2
cnt3 = count_flow3_pairs(csr, n, m, edges, bel0) # 待删边仍 2-边连通 = flow >= 3
print(cnt1 + cnt2 + cnt3)
if __name__ == "__main__":
solve()C++ 版(同一算法,用计数排序做精化):
/**
* 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:29
* update_at: 2026-10-07 20:29
*/
// main.cpp:一本通 1731《最大流》(同 CERC 2015 J "Juice Junctions")
// 无向图每个点度数 <= 3、每条边容量 1,求所有点对 i<j 间最大流之和。
// 由最大流最小割定理:端点度为 d 的点对流不超过 min(d(u),d(v)) <= 3,故流量 ∈ {0,1,2,3}。
// flow >= 1 <=> 两点在原图中连通(并查集);
// flow >= 2 <=> 两点属于同一「边双连通分量」(删掉桥以后的块);
// flow >= 3 <=> 删去任意一条边后,两点仍属同一边双连通分量。
// 记 cntk = #{(i<j) : flow(i,j) >= k},则答案 = cnt1 + cnt2 + cnt3。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3005; // 点数上限 3000
const int MAXM = 4505; // 边数上限 floor(3n/2) = 4500
int n, m; // 点数、边数
int eu[MAXM], ev[MAXM]; // 第 i 条边的两个端点(边编号 0..m-1)
// 链式前向星:每条无向边登记两次,edgeIdx 记回原始边号
int head[MAXN], nxt[2 * MAXM], to[2 * MAXM], edgeIdx[2 * MAXM], tot;
int dfn[MAXN], low[MAXN]; // Tarjan 时间戳与追溯值
int parEdge[MAXN]; // 每个点从父亲下来的那条边号
int cur[MAXN]; // 迭代式 DFS 的邻接边游标
char isBridge[MAXM]; // 该边是否为原图(或删边后图)的桥
int bel[MAXN]; // 每个点的边双连通分量编号(bel 是原图的划分,供 cnt2 与挑非桥边用)
int belNow[MAXN]; // 删边后本轮新算出的分量编号
int stk[MAXN], estk[MAXN]; // 迭代 DFS 的顶点栈与入边栈
int cls[MAXN]; // 等价类精化过程中的当前类编号
int ord1[MAXN], ord2[MAXN]; // 计数排序用的顺序数组
int cntArr[MAXN + 2]; // 计数排序的桶
// 加边:u、v 之间连一条编号为 id 的边
void addEdge(int id, int u, int v) {
tot++;
to[tot] = v;
edgeIdx[tot] = id;
nxt[tot] = head[u];
head[u] = tot;
}
// 求「删去第 ban 条边」后图的边双连通分量编号,写入 out[1..n](ban < 0 表示不删边)。
// 迭代式 Tarjan 标出所有桥,再忽略桥与被删边做 flood-fill,每个连通块即一个分量。
void edgeBiconnected(int ban, int out[]) {
for (int i = 1; i <= n; i++) {
dfn[i] = 0;
low[i] = 0;
cur[i] = head[i];
out[i] = 0;
parEdge[i] = -1;
}
for (int i = 0; i < m; i++) isBridge[i] = 0;
int timer = 0;
for (int s = 1; s <= n; s++) { // 图可以不连通,逐连通块 DFS
if (dfn[s]) continue;
int top = 0;
dfn[s] = low[s] = ++timer;
stk[top] = s;
estk[top] = -1;
top++;
while (top > 0) {
int u = stk[top - 1];
if (cur[u]) { // 还有没走过的邻边
int e = cur[u];
cur[u] = nxt[e];
int id = edgeIdx[e];
if (id == ban) continue; // 这条边被删掉了
int v = to[e];
if (!dfn[v]) { // 树边:把 v 压栈,稍后回溯时判桥
dfn[v] = low[v] = ++timer;
parEdge[v] = id;
stk[top] = v;
estk[top] = id;
top++;
} else if (id != parEdge[u] && dfn[v] < low[u]) {
low[u] = dfn[v]; // 回边,指向祖先
}
} else { // 回溯:u 的子树已经处理完
top--;
int pe = estk[top];
if (top > 0) {
int p = stk[top - 1];
if (low[u] > dfn[p]) isBridge[pe] = 1; // 树边 (p,u) 是桥
if (low[u] < low[p]) low[p] = low[u];
}
}
}
}
int comp = 0;
for (int s = 1; s <= n; s++) { // 忽略桥与被删边,逐块染色
if (out[s]) continue;
out[s] = ++comp;
int sp = 0;
stk[sp++] = s;
while (sp > 0) {
int u = stk[--sp];
for (int e = head[u]; e; e = nxt[e]) {
int id = edgeIdx[e];
if (id == ban || isBridge[id]) continue;
int v = to[e];
if (!out[v]) {
out[v] = comp;
stk[sp++] = v;
}
}
}
}
}
// 统计「编号相同的点对」个数:某等价关系下的点对数 C(k,2) 之和
ll countEqualPairs(int a[]) {
static int buf[MAXN];
for (int i = 1; i <= n; i++) buf[i - 1] = a[i];
sort(buf, buf + n);
ll res = 0;
for (int i = 0; i < n; ) {
int j = i;
while (j < n && buf[j] == buf[i]) j++;
ll c = j - i;
res += c * (c - 1) / 2;
i = j;
}
return res;
}
// 把等价类按 (cls, belNow) 两元组重新编号:两趟计数排序,等价类只会被细分,绝不合并。
// 好处是全程确定性(不依赖哈希),且每轮代价 O(n)。
void refine(int maxCls) {
// 第一趟:按 belNow 稳定排序(belNow ∈ [1, n])
for (int i = 0; i <= n + 1; i++) cntArr[i] = 0;
for (int v = 1; v <= n; v++) cntArr[belNow[v]]++;
int sum = 0;
for (int i = 0; i <= n + 1; i++) {
int c = cntArr[i];
cntArr[i] = sum;
sum += c;
}
for (int v = 1; v <= n; v++) ord1[cntArr[belNow[v]]++] = v;
// 第二趟:在 bel 有序的基础上按 cls 稳定排序,得到 (cls, bel) 的字典序
for (int i = 0; i <= maxCls + 1; i++) cntArr[i] = 0;
for (int i = 0; i < n; i++) cntArr[cls[ord1[i]]]++;
sum = 0;
for (int i = 0; i <= maxCls + 1; i++) {
int c = cntArr[i];
cntArr[i] = sum;
sum += c;
}
for (int i = 0; i < n; i++) ord2[cntArr[cls[ord1[i]]]++] = ord1[i];
// 相邻两个 (cls, bel) 只要不同就开一个新类
int r = 0;
for (int i = 0; i < n; i++) {
int v = ord2[i];
if (i > 0) {
int u = ord2[i - 1];
if (cls[v] != cls[u] || belNow[v] != belNow[u]) r++;
}
cntArr[v] = r; // 先借用 cntArr 暂存新编号
}
for (int v = 1; v <= n; v++) cls[v] = cntArr[v];
}
// 并查集(路径折半),只用来数连通分量
int fa[MAXN];
int findRoot(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
int main() {
if (scanf("%d %d", &n, &m) != 2) return 0;
tot = 0;
for (int i = 1; i <= n; i++) head[i] = 0;
for (int i = 0; i < m; i++) {
int x, y;
if (scanf("%d %d", &x, &y) != 2) return 0;
eu[i] = x;
ev[i] = y;
addEdge(i, x, y);
addEdge(i, y, x);
}
// ---- cnt1:连通分量 -> flow >= 1 的点对数 ----
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
int a = findRoot(eu[i]);
int b = findRoot(ev[i]);
if (a != b) fa[a] = b;
}
for (int i = 1; i <= n; i++) cls[i] = findRoot(i);
ll cnt1 = countEqualPairs(cls);
// ---- cnt2:原图的边双连通分量 -> flow >= 2 的点对数 ----
edgeBiconnected(-1, bel);
ll cnt2 = countEqualPairs(bel);
// ---- cnt3:每删一条「非桥边」做一次精化 -> flow >= 3 的点对数 ----------------
// 删掉一条桥不会改变原图的边双划分(删边只会让划分变细、不可能合并,
// 而桥不在任何非平凡边双块的内部),所以桥无需检验。
for (int v = 1; v <= n; v++) cls[v] = 0;
ll cnt3 = 0;
if (m > 0) {
int nonBridge = 0;
for (int i = 0; i < m; i++)
if (bel[eu[i]] == bel[ev[i]]) nonBridge++; // 非桥:两端点在同一分量
if (nonBridge > 0) {
int maxCls = 0;
for (int ban = 0; ban < m; ban++) {
if (bel[eu[ban]] != bel[ev[ban]]) continue; // 桥跳过
edgeBiconnected(ban, belNow);
refine(maxCls);
maxCls = 0;
for (int v = 1; v <= n; v++)
if (cls[v] > maxCls) maxCls = cls[v];
if (maxCls == n - 1) break; // 全是单点,再分下去 cnt3 必然是 0
}
cnt3 = countEqualPairs(cls);
}
}
printf("%lld\n", cnt1 + cnt2 + cnt3);
return 0;
}复杂度
- 时间:本层的划分各自都是
的 Tarjan/flood-fill; 那一层 在 C++ 里用并查集 、在 Python 里就是一次 flood-fill ; 最多做 轮,总计 。最坏数据 时约 次基本操作,C++ 实测 0.20 s,远低于 3 s 限时。 - 空间:邻接表
,Tarjan 的 dfn/low/cur、bel、cls等各, 总计 , 时不到 1 MB,与 256 MB 的限值差得很远。 - 与 C++ 解法的关系:
main.cpp与main.py是同一算法(三层判据、精化轮数都相同), 只是把 Python 的dict去重换成了 C++ 的两趟计数排序、把 Python 的 flood-fill 连通分量换成了 C++ 的并查集。 - Python 的 TLE 风险:算法同阶,但 CPython 的解释器常数大,
轮 Tarjan 的实测耗时 在顶格数据( )上约 8 s,会超过 3 s 的限时;中等规模 ( )在一秒内。按 oj-python-style的约定,这里允许 Python TLE, 但算法不允许降级——所以 Python 版仍是的 Tarjan 精化, 而不是退化成枚举点对求最大流。
总结
- 先用割的大小卡住值域。 “度数不超过
"这句约束的全部价值在于把答案从 个 小整数压成 四档;一旦想到"答案 ”, 逐对求最大流的 就瓦解了。 - 三层判据都是连通性的变体。 连通(并查集)→
-边连通(边双分量)→ “删任意一条边后仍 -边连通”( 次边双划分的交)。Menger 定理把"边不相交路径数" 和"最小割大小"在每一层上对应起来,所以三个 的判定全都只依赖图的划分结构。 - 数点对就是数等价类。 三层的答案都是同一句话:“在某等价关系下同编号的点对数”, 于是三处代码可以共用同一个计数函数,这也是本题代码能压得很短的原因。
- 迭代式 Tarjan。 Python 默认递归深度只有约
, 的链就会爆栈; 用显式栈写 Tarjan 是本题 Python 版能跑通的必要条件,同时也顺手绕开了 C++ 的爆栈风险。
关于本题数据的说明
本题的测试数据由素材源目录里的 data.py(基于 cyaron 的分层生成器)自造,
而非官方原题数据,题面也属网络重建;生成器对每组数据都给出了独立的闭式期望答案,
与前文三层判据的推导一致(例如点 10 是 main.cpp 与 main.py 在本目录数据上的通过,只说明实现与题面的推导自洽,
不等价于官方数据 AC。
图示解析
三层判据在一张「稠密块 + 桥」的图上表现最清楚:块内点对流量高,跨桥点对流量掉到
flowchart LR
subgraph K4["点 1,2,3,4 构成 K4"]
A["1"] --- B["2"]
A --- C["3"]
A --- D["4"]
B --- C
B --- D
C --- D
end
D --- E["5"]
E --- F["6"]