阅读程序(第二题):拓扑排序 + DAG 最长路

dx580079 组合题 共 个子题

阅读下面程序,完成后面的判断题和单选题。判断题正确填 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。( )

A

正确

B

错误

子题 判断题

判断题:以上述输入运行程序,输出为 7 5。( )

A

正确

B

错误

子题 判断题

判断题:若把第 26 行的 `if (--indeg[v] == 0) q[t++] = v;` 改为 `if (indeg[v] == 0) q[t++] = v;`(即去掉自减),其余不变,则以上述输入运行程序,输出的两个数都会变小。( )

A

正确

B

错误

子题 判断题

判断题:程序中 dist[u] 的值表示“以结点 u 为终点、以某个入度为 0 的结点为起点”的最长路径所包含的边数。( )

A

正确

B

错误

子题 单选题

以上述输入运行程序,dist[6] 的值为( )。

A

2

B

3

C

4

D

5

子题 单选题

以上述输入运行程序,程序第二个输出的值为( )。

A

3

B

4

C

5

D

7

子题 单选题

该程序的时间复杂度为( )。

A

Θ(n²)

B

Θ(n + m)

C

Θ(m log n)

D

Θ(nm)

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧