第36696题 组合题
阅读程序(第二题):拓扑排序 + 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;
}
{{ option.label }}
子题{{ index + 1 }} {{ child.type_label }}
{{ option.label }}
✓ 正确 ◐ 部分正确 ✗ 错误
程序运行统计
暂无判题统计
知识点:
提交{{ questionInfo.stats ? questionInfo.stats.submit_count : 0 }}次 正确率{{ statsAccuracy }}%
答案解析