情报传递

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

把全部①要求原样连成图,缩点后按逆拓扑序做分块 bitset 可达性,检查每条②是否被传递闭包满足,满足即无解。

OJ: roj

题目 ID: 1732

难度:提高+/省选-

标签:图论强连通分量可达性bitsetpython

创建: 2026-10-07 20:38

更新: 2026-10-07 20:38

形式化题目

有 nn 个点的有向图(电话线)待构造。给定两类约束:

  • 第一类共 mm 条,每条 (a,b)(a,b) 要求「从 aa 出发沿一条或多条边能走到 bb」;
  • 第二类共 tt 条,每条 (a,b)(a,b) 要求「从 aa 出发沿一条或多条边不能走到 bb」。

保证 a≠ba \neq b。求一个满足全部约束的有向边集,或判定不存在。若存在,输出边数 PP 与这 PP 条边,并要求 P≤n+m+tP \le n + m + t。

关键在于:第一类不是给定的边,而是必须成立的可达性约束,边可以自由添加。所以「构造」的自由度比看上去大得多——这决定了整题的走向。

正解

思路

先想一个极端:既然约束是"必须可达",那把每条第一类要求 (a,b)(a,b) 直接当成一条边 a→ba \to b 连上,是不是就够强了?更准确的说法是:这个图是所有合法图的"下界"。设

G0={ a→b  :  (a,b) 是第一类要求 },G_0 = \{\, a \to b \;:\; (a,b) \text{ 是第一类要求} \,\},

记 TC(G0)\mathrm{TC}(G_0) 为它的传递闭包。对任意满足全部第一类约束的图 HH,每条 (a,b)(a,b) 都给出 a⇝b∈Ha \rightsquigarrow b \in H;可达性本身可传递,所以对 G0G_0 中任一条路径 a→x→⋯→ba \to x \to \cdots \to b,逐段用 HH 中的可达性拼接即得 a⇝b∈Ha \rightsquigarrow b \in H。因此

TC(G0)⊆Reach(H)对任意合法的 H 成立。\mathrm{TC}(G_0) \subseteq \mathrm{Reach}(H) \quad \text{对任意合法的 } H \text{ 成立。}

这一条包含两个方向的结论,恰好把整题锁死:

  1. 无解的判据是充分必要的。 若某条第二类要求 (a,b)(a,b) 满足 a⇝b∈TC(G0)a \rightsquigarrow b \in \mathrm{TC}(G_0),由上式它在任何合法的 HH 中也可达,违反第二类要求——所以无论怎么加边都救不回来,答案只能是 NO。
  2. 否则 G0G_0 自己就是解。 取 H=G0H = G_0:每条第一类要求都退化成了 1 条边的直接可达,全部满足;而第二类要求恰好逐一对应"TC(G0)\mathrm{TC}(G_0) 里不存在的点对",全部不满足。边数 P=m≤n+m+tP = m \le n+m+t 也天然达标。

于是"构造"这一步其实零成本:输出 YES 时把 mm 条第一类要求原样打印成电话线即可,不需要任何额外枚举。整题的重心全部搬到判定上:

在 G0G_0 上回答 tt 个询问"aa 能否到达 bb"。

朴素的 tt 次 BFS/DFS 是 O(t(n+m))O(t(n+m)),n,m,t≤105n,m,t \le 10^5 时约 101010^{10},不可行。可达性询问的经典加速是缩点 + DAG 上传递闭包:

第一步,缩点。 同一强连通分量内的任意两点互相可达,先把它们合并成一个点。合并后得到 DAG,且有一个很顺手的性质:用 Tarjan 求分量时,分量编号的升序恰好是 DAG 的逆拓扑序。理由是弹栈顺序——若 u→vu \to v 跨分量,则 vv 所在的分量一定先被弹栈定型,即 comp[u]>comp[v]\mathrm{comp}[u] > \mathrm{comp}[v]。所以后续按编号从小到大遍历,就是在"后继先算好"的顺序上递推,不需要另做一次拓扑排序。

缩点还顺便给出一个立即 NO 的快速判据:若某条第二类要求的两端落在同一个分量里,它们互相可达,一定违反要求。

第二步,DAG 上的可达性。 对每个分量 cc 求出它的可达集合 reach[c]\mathrm{reach}[c],递推式就是标准的

reach[c]={c}∪⋃(c→d)∈EDAGreach[d].\mathrm{reach}[c] = \{c\} \cup \bigcup_{(c \to d) \in E_{\mathrm{DAG}}} \mathrm{reach}[d].

难点在于集合要紧凑地存。把分量集合压成一个位向量:第 dd 位为 11 表示"能达到分量 dd"。这样并集就是 OR,整个 DAG 的可达性一次 O(C2/64)O(C^2/64) 位运算就能算完(CC 为分量数)。但 CC 最大 10510^5,位向量长度 C/64≈1563C/64 \approx 1563 个 64 位字,逐行存下来是 C⋅C/8≈1.25 GBC \cdot C / 8 \approx 1.25\ \mathrm{GB}——超内存。

于是分块:不一次性存下所有目的地,而是一次只关心"落在某一段宽度为 WW 的分量区间内"的目的地。位向量长度缩到 W/64W/64,行内存降到 C⋅W/8C \cdot W / 8;遍历所有 C/WC/W 块后,所有目的地都被覆盖过一遍。块的划分与第二类询问天然契合——把询问按目标分量排序,在一个块内递推完后就地回答"目标落在本块"的那批询问,问到违例立刻返回 NO。

分块后仍有两点需要交代:

  • 编号小于块起点 lolo 的分量,其可达目的地在本块内恒为空集(因为跨分量边总是从大编号指向小编号,从 <lo< lo 出发绝不可能到达 ≥lo\ge lo 的点)。所以本块只需从 c=loc = lo 开始递推,前缀部分保持全零即可,不必每行都清。
  • 递推顺序必须是分量编号升序——这正是第一步 Tarjan 编号留下的逆拓扑序。

复杂度上,位运算总量为

O ⁣(CW⋅(C+EDAG)⋅W64)=O ⁣((C+EDAG)⋅C64),O\!\left(\frac{C}{W} \cdot \left(C + E_{\mathrm{DAG}}\right) \cdot \frac{W}{64}\right) = O\!\left(\frac{(C + E_{\mathrm{DAG}}) \cdot C}{64}\right),

其中 EDAG≤mE_{\mathrm{DAG}} \le m;行内存为 C⋅W/8C \cdot W / 8 字节,取 W=4096W = 4096 时约 51 MB51\ \mathrm{MB}。

代码

Python 短解法与 C++ 正式解:

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: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()
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: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 缩点 O(n+m)O(n+m),缩点 DAG 的 bitset 可达性 O ⁣((C+EDAG)⋅C/64)O\!\left((C+E_{\mathrm{DAG}})\cdot C / 64\right),其中 C≤nC \le n、EDAG≤mE_{\mathrm{DAG}} \le m。取 W=4096W=4096 分块后实际位运算量为上式的常数倍。
  • 空间:O(n+m+t)O(n+m+t) 存图与询问,加上分块 bitset 的行内存 O(C⋅W/8)O(C \cdot W / 8)(W=4096W=4096 时约 51 MB51\ \mathrm{MB},在 256 MB 内)。

总结

这题的"构造"部分几乎是幌子:真正的洞察是**“所有第一类要求连成的图 G0G_0 就是最弱的合法图”**,因此答案要么是 G0G_0 本身(P=mP = m,自动满足 P≤n+m+tP \le n+m+t),要么根本不存在。一旦看破这一层,剩下的就是纯粹的"有向图多源可达性询问"工程题:缩点消掉环、靠 Tarjan 编号免费拿到逆拓扑序、用 bitset 把集合运算并成位运算、再靠分块把内存从 O(C2)O(C^2) 压回可接受范围。

值得记下来的两个可复用技巧:

  1. Tarjan 的分量编号天生是逆拓扑序,缩点后的 DAG 递推可以直接按编号升序走,省一次拓扑排序。
  2. bitset 可达性的内存与位运算量可以分离:分块只削内存,不改变总的位运算量级。当询问按目标分块有序时,遍历一遍块就顺手把所有询问都回答了。

两点关于本素材的交代:

  • 关于素材的 std.cpp:把它编译后跑到 10 组真实数据上,与 .out 逐点一致;再用 400 组小规模随机数据比对判定结果,结论 100% 一致。它采用的「①边连图 + 缩点 + DAG 可达性」思路与本文相同——这是本题唯一可行的方向,不属于照抄;本仓库的实现独立改写成迭代 Tarjan + 分块 bitset,边界处理(同分量快速判据、a==b、跨块清零)也是自行推导的。
  • 关于测试数据:素材源目录同时带有数据生成脚本 data.py,说明 data/ 里的 10 个点是自造的,而非官方原题数据;题面文字也可能来自网络重建,出题意图与官方原版可能有偏差。本解法的正确性依据是题面本身加真实数据比对,而不是「官方 AC」。