第 1 题 有向图的强连通分量（SCC）中，以下哪种描述正确？ {{ select(1) }}

• SCC 内每个节点都能到达图中所有其他节点
• 每个节点恰好属于一个 SCC，且 SCC 内任意两点互相可达
• SCC 内节点数至少为 2
• 一个有向图只有一个 SCC

第 2 题 将有向图所有 SCC 缩点后，得到的新图是？ {{ select(2) }}

• 无向连通图
• 强连通图
• 有向无环图（DAG）
• 完全有向图

第 3 题 P2002"消息扩散"缩点后 DAG 有 4 个节点，入度分别为 [1, 0, 2, 0]，至少需要几个起点才能覆盖所有节点？ {{ select(3) }}

• 1
• 4
• 2
• 3

第 4 题 差分约束中，约束 xᵢ - xⱼ ≤ c，在 SPFA 最短路框架下应建一条？ {{ select(4) }}

• 从 j 到 i 的边，权值 c
• 从 i 到 j 的边，权值 c
• 从 j 到 i 的边，权值 -c
• 从 i 到 j 的边，权值 -c

第 5 题 树链剖分中，对节点 v 整棵子树内所有节点加 c，对应线段树的区间是（dfn[v] 为 v 的时间戳，sz[v] 为子树大小）？ {{ select(5) }}

• [dfn[v], dfn[v] + sz[v] − 1]
• [dfn[v] − sz[v] + 1, dfn[v]]
• [dfn[v], dfn[v] + depth[v]]
• [1, dfn[v]]

第 6 题 树链剖分跳链时，将 u 跳向其父节点之前，对线段树进行的区间操作是（top[u] 为 u 所在链顶节点）？ {{ select(6) }}

• [dfn[top[u]], dfn[u]]
• [dfn[u], dfn[top[u]]]
• [dfn[u], dfn[u] + sz[u] − 1]
• [dfn[top[u]], dfn[top[u]] + sz[top[u]] − 1]

第 7 题 T1513"受欢迎的牛"缩点后得到 4 个 SCC，大小为 [5, 3, 2, 4]，出度为 [0, 1, 0, 2]，答案是？ {{ select(7) }}

• 5
• 7
• 9
• 0

第 8 题 用 SPFA 判断差分约束系统无解（存在负环），正确的判断条件是？ {{ select(8) }}

• 存在节点的 dist 值为负数
• 图中存在负权边
• 某节点的入队次数 ≥ n + 1（n 为节点总数）
• SPFA 结束时仍有节点未被访问

第 9 题 树链剖分求 LCA，while (top[u] != top[v]) 循环结束后，top[u] == top[v]，此时 LCA 是？ {{ select(9) }}

• 一定是 u
• 一定是 v
• top[u]（即链顶节点）
• depth 较小的那个（depth[u] < depth[v] ? u : v）

第 10 题 以下两类差分约束，分别应运行最短路还是最长路？ ① 约束形如 xᵢ - xⱼ ≤ c（上界约束，P1993 类型） ② 约束形如 xᵢ - xⱼ ≥ k（下界约束，T1511 类型） {{ select(10) }}

• ①最短路，②最短路
• ①最短路，②最长路
• ①最长路，②最短路
• ①最长路，②最长路