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