第 1 题

Tarjan 算法中，dfn[x] 的含义是（　　）

{{ select(1) }}

• x 所在强连通分量的编号
• x 在 DFS 树中的深度
• x 第一次被访问的时间戳（DFS 序）
• x 能回到的最早祖先的 dfn

---

第 2 题

在有向图中，若任意两个顶点之间都存在双向路径，则该图是（　　）

{{ select(2) }}

• 强连通图
• 弱连通图
• 双连通图
• 完全图

---

第 3 题

下列关于「桥」的说法，正确的是（　　）

{{ select(3) }}

• 桥一定是割边，但割边不一定是桥
• 删除桥后，图的连通分量数增加
• 桥只存在于有向图中
• 每条边都是桥的图一定是树

---

第 4 题

一棵树有 7 个叶子节点，要使整棵树变成边双连通图，最少需要加（　　）条边

{{ select(4) }}

• 3
• 4
• 5
• 7

---

第 5 题

Tarjan 算法中，判定非根节点 x 为割点的条件是存在孩子 y 满足（　　）

{{ select(5) }}

• low[y] > dfn[x]
• low[y] >= dfn[x]
• dfn[y] >= low[x]
• low[x] > dfn[y]

---

第 6 题

将 SCC 缩点后，得到的新图的结构是（　　）

{{ select(6) }}

• 树
• 有向无环图（DAG）
• 无向图
• 完全图

---

第 7 题

在无向图中，DFS 树上有一条树边 (x, y)，其中 y 是 x 的儿子。用 Tarjan 求桥时，判定边 (x, y) 是桥的条件是（　　）

{{ select(7) }}

• low[y] >= dfn[x]
• low[y] > dfn[x]
• low[y] < dfn[x]
• dfn[y] < low[x]

---

第 8 题

一个有向图的 SCC 缩点成 DAG 后，若某个 SCC 的入度为 0，则（　　）

{{ select(8) }}

• 该 SCC 内的节点都是源点
• 从其他任何 SCC 都无法到达该 SCC
• 该 SCC 一定只包含一个节点
• 该 SCC 内所有节点在原图中入度都为 0

---

第 9 题

在 Tarjan 求 SCC 时，if (dfn[x] == low[x]) 这一条件的作用是（　　）

{{ select(9) }}

• 判断 x 是否为割点
• 判断一条边是否为桥
• 识别 SCC 的“根”，弹栈收集该分量所有节点
• 判断图是否连通

---

第 10 题

关于 2-SAT 问题，若要求「x 为真 或 y 为假」成立，即满足子句 x ∨ ¬y，则需要加入的蕴含边是（　　）

{{ select(10) }}

• ¬x → y 和 x → ¬y
• x → ¬y 和 y → x
• ¬x → ¬y 和 y → x
• ¬x → y 和 ¬y → x