阅读程序(第二题):拓扑排序 + DAG 最长路
阅读下面程序,完成后面的判断题和单选题。判断题正确填 A,错误填 B。
程序读入一个含 n 个点、m 条边的有向图(结点编号 1 ~ n),随后执行拓扑排序,并在拓扑序上递推“以每个结点结尾的最长路径边数”。输出两个整数:进入拓扑序列的结点个数 t,以及所有 dist 的最大值。以下各题若无特别说明,均以输入
7 8
1 2
1 3
2 4
3 4
4 5
5 6
3 6
6 7
为例。
#include <cstdio>
const int MAXN = 100005;
int head[MAXN], nxt[MAXN], to[MAXN], tot;
int indeg[MAXN], q[MAXN], dist[MAXN];
void add(int u, int v) { nxt[++tot] = head[u]; to[tot] = v; head[u] = tot; }
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
++indeg[v];
}
int h = 0, t = 0;
for (int i = 1; i <= n; ++i)
if (indeg[i] == 0) q[t++] = i;
while (h < t) {
int u = q[h++];
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if (dist[u] + 1 > dist[v]) dist[v] = dist[u] + 1;
if (--indeg[v] == 0) q[t++] = v;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i)
if (dist[i] > ans) ans = dist[i];
printf("%d %d\n", t, ans);
return 0;
} 子题 判断题
判断题:该程序可以处理含有向环的图,不会陷入死循环;此时输出的第一个数小于 n。( )
子题 判断题
判断题:以上述输入运行程序,输出为 7 5。( )
子题 判断题
判断题:若把第 26 行的 `if (--indeg[v] == 0) q[t++] = v;` 改为 `if (indeg[v] == 0) q[t++] = v;`(即去掉自减),其余不变,则以上述输入运行程序,输出的两个数都会变小。( )
子题 判断题
判断题:程序中 dist[u] 的值表示“以结点 u 为终点、以某个入度为 0 的结点为起点”的最长路径所包含的边数。( )
子题 单选题
以上述输入运行程序,dist[6] 的值为( )。
子题 单选题
以上述输入运行程序,程序第二个输出的值为( )。
子题 单选题
该程序的时间复杂度为( )。
正在加载题目数据…
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析