Problem E: [CSP-S1][程序阅读] 程序阅读5
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：135
Solved：14
Description
给定一个有向无环图（DAG），以下代码通过删除入度为0的顶点的出边实现拓扑排序。请仔细阅读代码并回答问题。
2. 若输入图中存在自环（如边`u→u`），代码会输出"Cycle detected"。 ( )
3. 删除边`u→v`的操作是通过`adj.erase(v)`实现的。 ( )
4. 若输入图的边为`1→2`, `2→3`, `1→3`，则`cnt`的最终值为3。 ( )
5. 队列`q`的出队顺序即为一种合法的拓扑序。
选择题
1. 对于输入`n=3, m=2`，边为`1→2`, `2→3`，代码输出的结果是：
A. Cycle detected
B. Valid topological order
C. 运行错误
D. 无输出
2. 若输入`n=4, m=3`，边为`1→2`, `2→3`, `3→1`，则`cnt`的最终值为：
A. 0
B. 3
C. 4
D. 无法确定
3. 代码中`inDegree[v]--`的作用是：
A. 物理删除边`u→v`
B. 减少顶点`v`的入度
C. 标记顶点`v`为已访问
D. 将`v`加入队列
4. 若将`queue<int>`替换为`stack<int>`，则：
A. 结果一定错误
B. 结果可能不同但正确
C. 无法处理环
D. 会输出逆拓扑序
5. 对于输入`n=4, m=4`，边为`1→2`, `1→3`, `2→4`, `3→4`，队列`q`的入队顺序可能是：
A. 1,2,3,4
B. 1,4,2,3
C. 2,1,3,4
D. 4,3,2,1
|
#include <iostream> #include <vector>#include <queue> using namespace std; const int MAXN = 1e5 + 5; vector<int> adj[MAXN]; int inDegree[MAXN], n, m; void topologicalSort() { queue<int> q; for (int i = 1; i <= n; ++i) if (inDegree[i] == 0) q.push(i); int cnt = 0; while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (int v : adj) { inDegree[v]--; if (inDegree[v] == 0) q.push(v); } } if (cnt != n) cout << "Cycle detected\n"; else cout << "Valid topological order\n"; } int main() { cin >> n >> m; for (int i = 0, u, v; i < m; ++i) { cin >> u >> v; adj.push_back(v); inDegree[v]++; } topologicalSort(); return 0; } |
判断题
1. 代码中通过队列`q`存储的始终是当前入度为0的顶点。 ( )2. 若输入图中存在自环（如边`u→u`），代码会输出"Cycle detected"。 ( )
3. 删除边`u→v`的操作是通过`adj.erase(v)`实现的。 ( )
4. 若输入图的边为`1→2`, `2→3`, `1→3`，则`cnt`的最终值为3。 ( )
5. 队列`q`的出队顺序即为一种合法的拓扑序。
选择题
1. 对于输入`n=3, m=2`，边为`1→2`, `2→3`，代码输出的结果是：
A. Cycle detected
B. Valid topological order
C. 运行错误
D. 无输出
2. 若输入`n=4, m=3`，边为`1→2`, `2→3`, `3→1`，则`cnt`的最终值为：
A. 0
B. 3
C. 4
D. 无法确定
3. 代码中`inDegree[v]--`的作用是：
A. 物理删除边`u→v`
B. 减少顶点`v`的入度
C. 标记顶点`v`为已访问
D. 将`v`加入队列
4. 若将`queue<int>`替换为`stack<int>`，则：
A. 结果一定错误
B. 结果可能不同但正确
C. 无法处理环
D. 会输出逆拓扑序
5. 对于输入`n=4, m=4`，边为`1→2`, `1→3`, `2→4`, `3→4`，队列`q`的入队顺序可能是：
A. 1,2,3,4
B. 1,4,2,3
C. 2,1,3,4
D. 4,3,2,1