把全部①要求原样连成图,缩点后按逆拓扑序做分块 bitset 可达性,检查每条②是否被传递闭包满足,满足即无解。
OJ: roj
题目 ID: 1732
难度:提高+/省选-
标签:图论强连通分量可达性bitsetpython
创建: 2026-10-07 20:38
更新: 2026-10-07 20:38
形式化题目
有
- 第一类共
条,每条 要求「从 出发沿一条或多条边能走到 」; - 第二类共
条,每条 要求「从 出发沿一条或多条边不能走到 」。
保证
关键在于:第一类不是给定的边,而是必须成立的可达性约束,边可以自由添加。所以「构造」的自由度比看上去大得多——这决定了整题的走向。
正解
思路
先想一个极端:既然约束是"必须可达",那把每条第一类要求
记
这一条包含两个方向的结论,恰好把整题锁死:
- 无解的判据是充分必要的。 若某条第二类要求
满足 ,由上式它在任何合法的 中也可达,违反第二类要求——所以无论怎么加边都救不回来,答案只能是 NO。 - 否则
自己就是解。 取 :每条第一类要求都退化成了 1 条边的直接可达,全部满足;而第二类要求恰好逐一对应" 里不存在的点对",全部不满足。边数 也天然达标。
于是"构造"这一步其实零成本:输出 YES 时把
在
上回答 个询问" 能否到达 "。
朴素的
第一步,缩点。 同一强连通分量内的任意两点互相可达,先把它们合并成一个点。合并后得到 DAG,且有一个很顺手的性质:用 Tarjan 求分量时,分量编号的升序恰好是 DAG 的逆拓扑序。理由是弹栈顺序——若
缩点还顺便给出一个立即 NO 的快速判据:若某条第二类要求的两端落在同一个分量里,它们互相可达,一定违反要求。
第二步,DAG 上的可达性。 对每个分量
难点在于集合要紧凑地存。把分量集合压成一个位向量:第
于是分块:不一次性存下所有目的地,而是一次只关心"落在某一段宽度为 NO。
分块后仍有两点需要交代:
- 编号小于块起点
的分量,其可达目的地在本块内恒为空集(因为跨分量边总是从大编号指向小编号,从 出发绝不可能到达 的点)。所以本块只需从 开始递推,前缀部分保持全零即可,不必每行都清。 - 递推顺序必须是分量编号升序——这正是第一步 Tarjan 编号留下的逆拓扑序。
复杂度上,位运算总量为
其中
代码
Python 短解法与 C++ 正式解:
#!/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:45
# update_at: 2026-10-07 20:45
import sys
from itertools import groupby
# 核心结论:把全部①要求原样当边连成图 G0,则「合法情报网存在」⇔ 每条②要求 (a,b)
# 在 G0 里都不可达。因为可达性有传递性 ⇒ 任何合法图都必须包含 TC(G0);反过来取
# G = G0 就合法,而它的边数 = m ≤ n+m+t。于是问题只剩「①图上的 t 次可达性」。
# 缩点后:a 能到 b ⇔ comp[a] 能到 comp[b](同分量时恒真)。
BLK = 4096 # 可达性分块宽度:一次只追踪「编号落在 [lo, lo+BLK) 内」的目的地
type Edges = list[tuple[int, int]] # 要求表:每项是一个 (a, b) 点对
type Adj = list[list[int]] # 邻接表:Adj[u] 是 u 的出边终点列表
def load() -> tuple[int, Edges, Edges]:
"""按输入格式顺序取出 n、①要求表、②要求表。"""
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
m = next(data)
req1: Edges = [(next(data), next(data)) for _ in range(m)]
t = next(data)
req2: Edges = [(next(data), next(data)) for _ in range(t)]
return n, req1, req2
def scc(n: int, req1: Edges) -> tuple[list[int], int]:
"""Tarjan 求强连通分量,返回 (每个点的分量号, 分量总数)。
分量号按弹栈顺序给出:跨分量的边 u→v 恒满足 comp[u] > comp[v],
即分量号**升序**恰好是缩点 DAG 的逆拓扑序(后继都已算好)。
用显式调用栈代替递归,n=1e5 的链也不会爆栈。
"""
adj: Adj = [[] for _ in range(n + 1)]
for a, b in req1:
adj[a].append(b)
dfn = [0] * (n + 1)
low = [0] * (n + 1)
comp = [0] * (n + 1)
onstk = bytearray(n + 1)
stk: list[int] = [] # Tarjan 栈
timer = 0
cc = 0
for s in range(1, n + 1):
if dfn[s]:
continue
timer += 1
dfn[s] = low[s] = timer
stk.append(s)
onstk[s] = 1
call_node = [s] # 显式调用栈:节点
call_i = [0] # 与之平行:该节点下一条待访问的邻边下标
while call_node:
u = call_node[-1]
i = call_i[-1]
if i < len(adj[u]):
call_i[-1] = i + 1
v = adj[u][i]
if not dfn[v]:
timer += 1
dfn[v] = low[v] = timer
stk.append(v)
onstk[v] = 1
call_node.append(v)
call_i.append(0)
elif onstk[v] and dfn[v] < low[u]:
low[u] = dfn[v] # 回边:用 dfn 更新
else:
call_node.pop()
call_i.pop()
if low[u] == dfn[u]: # u 是所在 SCC 的根 → 弹栈定型
while True:
w = stk.pop()
onstk[w] = 0
comp[w] = cc
if w == u:
break
cc += 1
if call_node:
p = call_node[-1]
if low[u] < low[p]:
low[p] = low[u] # 子孙的 low 回传给父节点
return comp, cc
def dag_adj(comp: list[int], cnt: int, req1: Edges) -> Adj:
"""缩点后的 DAG 邻接表:去掉自环(同分量内永远互相可达),跨分量边去重。"""
seen: list[set[int]] = [set() for _ in range(cnt)]
for a, b in req1:
if comp[a] != comp[b]:
seen[comp[a]].add(comp[b])
return [list(s) for s in seen]
def violated(comp: list[int], cnt: int, nxt: Adj, req2: Edges) -> bool:
"""②要求是否有被①图的传递闭包满足:满足任意一条就说明无解。
先做快速判据:a、b 落在同一个分量 ⇒ 同属一个强连通分量、互相可达(a==b 时
还需分量里还有别的点才成环)⇒ 必然无解。
剩下的点对逐个用位集合判:缩点 DAG 上 c 的可达集第 d 位为 1 表示 comp[c] ⇝ comp[d]。
按目的地分块做,一次只保留落在一块 BLK 个分量内的目的地,按分量号升序递推
reach[c] = bit(c-lo) | ⋃ reach[d] (c→d 为跨分量边)
因为跨分量边总是从大编号指向小编号,升序递推时后继一定已经算好;编号 < lo 的
行在本块恒为 0,正好等价于「本块不追踪那些目的地」。
"""
csize = [0] * cnt
for c in comp[1:]:
csize[c] += 1
for a, b in req2:
ca, cb = comp[a], comp[b]
same_comp = ca == cb
if same_comp and (a != b or csize[ca] > 1):
return True
pairs = sorted((comp[b], comp[a]) for a, b in req2) # 按②的目标分量排序
for blk, grp in groupby(pairs, key=lambda p: p[0] // BLK):
lo = blk * BLK
hi = lo + BLK # 本块追踪的目的地区间 [lo, hi)
reach = [0] * cnt # 每个分量在本块内的可达目的地集合
for c in range(lo, cnt):
# 只有落在本块的目的地才登记成位;不在本块的 c 只继承后继的可达位
mask = 1 << (c - lo) if c < hi else 0
for d in nxt[c]:
mask |= reach[d]
reach[c] = mask
for target, src in grp:
# target == src 只可能是「a==b 且分量大小为 1」,已在快速判据里排除;
# 位集合里第 src 位总为 1,若不排除就会把「自己到自己」误判成可达。
reachable = src != target and reach[src] >> (target - lo) & 1
if reachable:
return True
return False
def solve() -> None:
n, req1, req2 = load()
comp, cnt = scc(n, req1)
out: list[str] = []
if violated(comp, cnt, dag_adj(comp, cnt, req1), req2):
out.append("NO")
else:
# G0 自己就是合法解:m 条①要求原样当电话线输出,P = m ≤ n+m+t
out += ["YES", str(len(req1))]
out += [f"{a} {b}" for a, b in req1]
sys.stdout.write("\n".join(out) + "\n")
if __name__ == "__main__":
solve()/**
* 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:38
* update_at: 2026-10-07 20:38
*/
// ROJ 1732《情报传递》 C++17(/opt/homebrew/bin/g++-16 -O2 编译)
// 限制:time 2000 ms / memory 256 MB
// ----------------------------------------------------------------------------
// 【题意】两类「要求」:① a 必须能到达 b;② a 必须不能到达 b(保证 a≠b)。
// 要求构造一个有向图(电话线)满足全部要求,或判定无解;
// 边的条数 P 需满足 P ≤ n+m+t。
// 【核心结论】
// 设 R1 = 全部①要求连成的边集,TC(R1) 为其传递闭包。对任意合法图 G:
// 每条①(a,b) 都要求 a⇝b ∈ G,而可达性传递 ⇒ 归纳得 TC(R1) ⊆ Reach(G)。于是
// • 若有②(a,b) 满足 a⇝b ∈ TC(R1),则任何 G 都违反② ⇒ NO;
// • 否则取 G = R1 即合法:①的每条要求都成了 1 条边,②要求的点对恰好是
// TC(R1) 里不存在的那些 ⇒ 全部满足 ⇒ YES,且 P = m1 ≤ n+m+t 恒成立。
// ⇒ 判定归结为:在「①要求图」上判断这 t 个点对是否可达。
// 【算法】
// 1. 迭代式 Tarjan 求 SCC(n=1e5 的链也不爆栈;不用递归、不动栈限制)。
// 弹栈顺序保证跨分量边 u→v 必有 comp[u] > comp[v],故按分量编号**升序**
// 递推即为「后继先算好」的正确顺序,无需另做拓扑排序。
// 2. ②的 a、b 落在同一分量 ⇒ 同属一个 SCC、互相可达 ⇒ 立即 NO(快速判据)。
// 3. 缩点得 DAG(去掉自环、跨分量边排序去重后建 CSR)。在 DAG 上做**分块
// bitset** 可达性:位空间 = 分量编号,一块 W 个分量,每行 W/64 个 u64,
// row[c] = bit(c-lo) | ∪ row[d](c→d 为跨分量边)。②询问按目标分量计数排序,
// 每块算完就地回答本块的询问;任何违例立即 NO 返回。
// 位运算量 ≈ Σ_blocks (C + E)·W/64 = O((C+E)·C/64),行内存 C·W/8 字节。
// 【样例】样例1 → NO;样例2 → YES / 2 / (1 2) (2 3),与题面逐字节一致。
// ----------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // n 的上限
const int BLK = 4096; // 可达性 bitset 的分块宽度(每块覆盖 BLK 个分量)
const int BLKW = BLK / 64;
// ------------------------------ 快速输入输出 ------------------------------
namespace io {
const int SZ = 1 << 20;
char buf[SZ];
int len = 0, pos = 0;
inline int gc() {
if (pos == len) {
len = (int)fread(buf, 1, SZ, stdin);
pos = 0;
if (len <= 0) return -1;
}
return buf[pos++];
}
inline int readInt() {
int c = gc();
while (c <= ' ' && c != -1) c = gc();
int x = 0;
while (c > ' ') { x = x * 10 + (c - '0'); c = gc(); }
return x;
}
inline void writes(const char* s) { fwrite(s, 1, strlen(s), stdout); }
} // namespace io
struct Arc { // 缩点 DAG 上的一条跨分量边,排序去重时按 (from, to) 比较
int from;
int to;
};
// 给 Arc 排序用的比较器(不用 lambda,便于阅读与调试)
bool arcLess(const Arc& x, const Arc& y) {
if (x.from != y.from) return x.from < y.from;
return x.to < y.to;
}
int n, m, t;
vector<int> adj[MAXN]; // ① 要求连成的有向图
int ea[MAXN], eb[MAXN]; // ① 要求的端点(YES 时原样输出成电话线)
int qa[MAXN], qb[MAXN]; // ② 要求的端点
int dfn[MAXN], low[MAXN], comp[MAXN], edgePtr[MAXN], compSize[MAXN];
int dfsStk[MAXN], stk[MAXN]; // dfsStk = 迭代 DFS 调用栈,stk = Tarjan 栈
unsigned char onstk[MAXN];
// 迭代式 Tarjan:返回强连通分量数。
// 编号规则:跨分量边 u→v 必有 comp[u] > comp[v](弹栈顺序即 DAG 的逆拓扑序)。
int tarjan() {
int timer = 0, cc = 0, top = 0;
for (int s = 1; s <= n; s++) {
if (dfn[s]) continue;
dfn[s] = low[s] = ++timer;
stk[top++] = s;
onstk[s] = 1;
int ctop = 0;
dfsStk[ctop++] = s;
while (ctop) {
int u = dfsStk[ctop - 1];
if (edgePtr[u] < (int)adj[u].size()) {
int v = adj[u][edgePtr[u]++];
if (!dfn[v]) {
dfn[v] = low[v] = ++timer;
stk[top++] = v;
onstk[v] = 1;
dfsStk[ctop++] = v;
} else if (onstk[v] && dfn[v] < low[u]) {
low[u] = dfn[v]; // 回边:用 dfn 更新 low
}
} else {
ctop--;
if (low[u] == dfn[u]) { // u 是所在 SCC 的根 → 弹栈定型
while (true) {
int w = stk[--top];
onstk[w] = 0;
comp[w] = cc;
if (w == u) break;
}
cc++;
}
if (ctop) { // 把子孙的 low 回传给父节点
int p = dfsStk[ctop - 1];
if (low[u] < low[p]) low[p] = low[u];
}
}
}
}
return cc;
}
Arc arcs[MAXN]; // 跨分量边(去重前)
int dagStart[MAXN + 1]; // CSR:分量 c 的出边在 dagTo[dagStart[c] .. dagStart[c+1])
int dagTo[MAXN];
int order[MAXN]; // ②询问按目标分量排序后的下标序列
int bucket[MAXN]; // 计数排序用的桶头
int main() {
n = io::readInt();
m = io::readInt();
for (int i = 1; i <= m; i++) {
int a = io::readInt(), b = io::readInt();
ea[i] = a;
eb[i] = b;
adj[a].push_back(b);
}
t = io::readInt();
for (int i = 1; i <= t; i++) { qa[i] = io::readInt(); qb[i] = io::readInt(); }
int C = tarjan();
for (int i = 1; i <= n; i++) compSize[comp[i]]++;
// 快速判据:②的 a、b 落在同一分量 ⇒ 同一 SCC 内互相可达 ⇒ 必违反②
//(题面保证 a≠b;a==b 时只有大小 > 1 的分量才必然可达)
bool bad = false;
for (int i = 1; i <= t && !bad; i++)
if (comp[qa[i]] == comp[qb[i]] && (qa[i] != qb[i] || compSize[comp[qa[i]]] > 1))
bad = true;
// ---- 缩点 DAG:收集跨分量边,排序去重,建 CSR ----
int acnt = 0;
for (int i = 1; i <= m; i++) {
int ca = comp[ea[i]], cb = comp[eb[i]];
if (ca != cb) { arcs[acnt].from = ca; arcs[acnt].to = cb; acnt++; }
}
sort(arcs, arcs + acnt, arcLess);
int E = 0;
for (int i = 0; i < acnt; i++)
if (i == 0 || arcs[i].from != arcs[i - 1].from || arcs[i].to != arcs[i - 1].to)
arcs[E++] = arcs[i]; // 就地压缩:每条 (from,to) 只留一次
for (int c = 0; c <= C; c++) dagStart[c] = 0;
for (int i = 0; i < E; i++) dagStart[arcs[i].from + 1]++;
for (int c = 0; c < C; c++) dagStart[c + 1] += dagStart[c];
for (int c = 0; c < C; c++) bucket[c] = dagStart[c]; // 借用成填充指针
for (int i = 0; i < E; i++) {
int c = arcs[i].from;
dagTo[bucket[c]++] = arcs[i].to;
}
// ---- ②询问按「目标分量」计数排序(目标分量是 [0,C) 内的整数)----
for (int c = 0; c <= C; c++) bucket[c] = 0;
for (int i = 1; i <= t; i++) order[comp[qb[i]]]++;
{
int acc = 0;
for (int c = 0; c < C; c++) {
int cnt = order[c];
order[c] = acc;
acc += cnt;
}
order[C] = acc;
}
for (int i = 1; i <= t; i++) bucket[order[comp[qb[i]]]++] = i;
for (int i = 1; i <= t; i++) order[i] = bucket[i - 1]; // order[1..t] 即排序结果
int qptr = 1;
if (!bad) {
vector<unsigned long long> reach((size_t)C * BLKW, 0); // 约 C·BLK/8 字节
for (int lo = 0; lo < C; lo += BLK) {
int hi = min(C, lo + BLK); // 本块追踪的目的地区间 [lo, hi)
// 整块清零:编号 < lo 的行在本块必须是全 0
//(跨分量边恒从大编号指向小编号,从 < lo 出发到不了 >= lo 的点)。
memset(reach.data(), 0, sizeof(unsigned long long) * (size_t)C * BLKW);
// 分量编号升序递推:c 的后继编号都更小,所以后继在本块已经算好
for (int c = lo; c < C; c++) {
unsigned long long* row = &reach[(size_t)c * BLKW];
if (c < hi) row[(c - lo) >> 6] |= 1ULL << ((c - lo) & 63);
for (int e = dagStart[c]; e < dagStart[c + 1]; e++) {
const unsigned long long* sr = &reach[(size_t)dagTo[e] * BLKW];
for (int w = 0; w < BLKW; w++) row[w] |= sr[w];
}
}
// 本块内回答所有「目标落在 [lo,hi)」的询问
while (qptr <= t && comp[qb[order[qptr]]] < hi) {
int i = order[qptr++];
// a==b 的询问已由上面的快速判据处理(看分量大小),此处跳过
if (qa[i] == qb[i]) continue;
int cb = comp[qb[i]] - lo;
int ca = comp[qa[i]];
if ((reach[(size_t)ca * BLKW + (cb >> 6)] >> (cb & 63)) & 1ULL) {
bad = true;
break;
}
}
if (bad) break;
}
}
// ---- 输出 ----
if (bad) {
io::writes("NO\n");
return 0;
}
// G0 自己就是合法解:m 条①要求原样当电话线输出,P = m ≤ n+m+t
io::writes("YES\n");
printf("%d\n", m);
for (int i = 1; i <= m; i++) printf("%d %d\n", ea[i], eb[i]);
return 0;
}复杂度
- 时间:Tarjan 缩点
,缩点 DAG 的 bitset 可达性 ,其中 、 。取 分块后实际位运算量为上式的常数倍。 - 空间:
存图与询问,加上分块 bitset 的行内存 ( 时约 ,在 256 MB 内)。
总结
这题的"构造"部分几乎是幌子:真正的洞察是**“所有第一类要求连成的图
值得记下来的两个可复用技巧:
- Tarjan 的分量编号天生是逆拓扑序,缩点后的 DAG 递推可以直接按编号升序走,省一次拓扑排序。
- bitset 可达性的内存与位运算量可以分离:分块只削内存,不改变总的位运算量级。当询问按目标分块有序时,遍历一遍块就顺手把所有询问都回答了。
两点关于本素材的交代:
- 关于素材的
std.cpp:把它编译后跑到 10 组真实数据上,与.out逐点一致;再用 400 组小规模随机数据比对判定结果,结论 100% 一致。它采用的「①边连图 + 缩点 + DAG 可达性」思路与本文相同——这是本题唯一可行的方向,不属于照抄;本仓库的实现独立改写成迭代 Tarjan + 分块 bitset,边界处理(同分量快速判据、a==b、跨块清零)也是自行推导的。 - 关于测试数据:素材源目录同时带有数据生成脚本
data.py,说明data/里的 10 个点是自造的,而非官方原题数据;题面文字也可能来自网络重建,出题意图与官方原版可能有偏差。本解法的正确性依据是题面本身加真实数据比对,而不是「官方 AC」。