推导式

OPPO 笔试真题 · 2023 秋招 · 后端岗

判题请到牛客原题提交。

题目描述

形如$1\rightarrow 3$这样的式子是推导式，说明结论$1$可以推导出结论$3$。

显然这样的推导式具有传递性：

如果$1\rightarrow 3$且$3\rightarrow 5$，那么肯定满足$1\rightarrow 5$ 。

现在给出$n$个推导式，你需要输出结论$c$能够推导出多少个不同的结论。 显然任何结论都可以推导出自己。

输入格式

第一行输入两个整数$n$和$c$，含义如题意所述。

接下来$n$行，每行输入两个整数$x,y$，表示一个推导式$x\rightarrow y$，可能会出现重复的推导式。

$(1\leq n \leq 10^5),(1\leq x,y,c \leq 10000)$

输出格式

输出一个整数，表示结论$c$能推导出的不同结论的数目。

示例

示例 1

输入：

5 1
1 2
1 3
3 9
4 2
8 1

输出：

4

说明：

根据推导式$1\rightarrow2,1\rightarrow3,3\rightarrow9$，可以判断出结论$1$可以推出结论$2,3,9$，加上本身总共$4$个结论。

示例 2

输入：

2 2
1 2
3 2

输出：

1

说明：

结论$2$不能推导出除了本身外的任何结论。

---

解题思路

第一步：把「推导」翻译成图论语言

把每个结论看成一个点，一条推导式 $x \to y$ 看成一条有向边。
题目说推导具有传递性（$1 \to 3$ 且 $3 \to 5$ 就有 $1 \to 5$），
这正好就是「沿有向边走任意多步」。于是问题变成：

从点 $c$ 出发，沿着有向边能走到多少个不同的点（含 $c$ 自己）。

第二步：为什么不能用并查集

并查集只能描述「无向连通」，会把 $x \to y$ 和 $y \to x$ 当成同一件事。
本题方向是有意义的：样例 1 里的 $8 \to 1$ 表示「8 能推出 1」，
并不能让 1 推出 8。若用并查集，1、2、3、4、8、9 会被并成一整块，
答案错成 6。

所以必须保留方向，做有向图上的可达性搜索。

第三步：一次 DFS/BFS 标记访问

从 $c$ 出发入栈，沿出边不断扩展，用 visited 数组记录已经到达的点：

• 第一次到达某个点时计数加 1；
• 已经访问过的点不再入栈（否则遇到环会死循环）。

搜索结束时，计数就是答案。

第四步：几个必须处理好的细节

• 重复的推导式：同一条边出现多次，visited 保证只算一次。
• 自环 $x \to x$：入栈后不会造成死循环，因为起点已标记。
• 环：$1 \to 2 \to 1$，靠 visited 终止。
• $c$ 不在任何推导式里：答案是 1（只有自己）。
• 结论编号最大 10000，直接开 10001 个桶的邻接表，比哈希表更快。

---

完整代码实现

import sys

MAX_ID = 10000


def solve() -> None:
    """从 c 出发沿有向边 DFS，数一数能到达多少个结点"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    pos = 0
    n = int(data[pos]); pos += 1
    c = int(data[pos]); pos += 1

    graph = [[] for _ in range(MAX_ID + 1)]
    for _ in range(n):
        x = int(data[pos]); y = int(data[pos + 1]); pos += 2
        graph[x].append(y)

    visited = [False] * (MAX_ID + 1)
    visited[c] = True
    stack = [c]
    count = 1
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                count += 1
                stack.append(v)

    sys.stdout.write(str(count) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

示例 1

5 1
1 2
1 3
3 9
4 2
8 1

从 1 出发：

步骤	当前点	沿边到达	已收集的结论
1	1	2、3	{1, 2, 3}
2	3	9	{1, 2, 3, 9}
3	2、9	无出边	{1, 2, 3, 9}

$8 \to 1$ 的方向是「指向 1」，不能反向使用；$4 \to 2$ 同理也到不了。
所以答案是 4。

示例 2

2 2
1 2
3 2

从 2 出发，2 没有任何出边（两条边都是指向 2 的），所以只能推出自己，
答案是 1。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
传递闭包（Floyd）	$O(V^3)$	$O(V^2)$	$V=10^4$，完全不可行
并查集	$O(n\,\alpha(n))$	$O(n)$	方向丢失，答案错误
有向图 DFS/BFS	$O(n + V)$	$O(n + V)$	推荐，每条边每个点只访问一次

---

易错点总结

1. 把有向边当成无向边

这是本题最大的陷阱。$x \to y$ 只表示 $x$ 能推出 $y$，反向不成立。
样例 1 的 $8 \to 1$ 就是专门用来检验这一点的。

2. 忘记把 $c$ 自己算进去

题面明确写了「显然任何结论都可以推导出自己」，所以计数从 1 开始，
visited[c] 一开始就置为 True。

3. 没有标记访问导致死循环

出现环（$1 \to 2 \to 1$）或自环时，不判重就会无限入栈。

4. 数组开小

结论编号上界是 10000，邻接表要开 10001 个位置（下标 0 空着不用）。
开成 10000 会在编号恰好为 10000 时越界。

5. 重复的推导式

题面说可能有重复，直接全部加进邻接表也没问题，visited 会去重；
不需要提前用 set 处理。

---

扩展思考

• 如果问题改成「哪些结论互相可以推导」，就需要求强连通分量
  （Tarjan / Kosaraju），同一个分量内的点两两可达。
• 如果要对每个点都回答一次「能推出多少个」，逐点 DFS 是
  $O(V(n+V))$；$V$ 较小时可以用 bitset 做传递闭包，把常数压下去。
• 「$S$ 能推出 $T$」的批量询问可以用拓扑序 + bitset 或离线做，本质仍是
  可达性。

---

相关题目

• 小欧皇