NOIP 提高 2017 第一轮 第 32 题：完善程序（大整数除法）第 1 空

题目

（最长路径）给定一个有向无环图，每条边长度为 $1$，求图中的最长路径长度。（第五空 2 分，其余 3 分）

输入：第一行是结点数 $n$（不超过 $100$）和边数 $m$，接下来 $m$ 行，每行两个整数 $a,b$，表示从结点 $a$ 到结点 $b$ 有一条有向边。结点标号从 $0$ 到 $(n-1)$。 输出：最长路径长度。

提示：先进行拓扑排序，然后按照拓扑序计算最长路径。

#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100];     // 记录每个结点的入度
int len[100];        // 记录以各结点为终点的最长路径长度
int queue[100];      // 存放拓扑排序结果
int main()
{
    cin >> n >> m;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            graph[i][j] = 0;
    for (i = 0; i < n; i++)
        degree[i] = 0;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b;
        graph[a][b] = 1;
        (1);
    }
    tail = 0;
    for (i = 0; i < n; i++)
        if ((2))
        {
            queue[tail] = i;
            tail++;
        }
    head = 0;
    while (tail < n - 1)
    {
        for (i = 0; i < n; i++)
            if (graph[queue[head]][i] == 1)
            {
                (3);
                if (degree[i] == 0)
                {
                    queue[tail] = i;
                    tail++;
                }
            }
        (4);
    }
    ans = 0;
    for (i = 0; i < n; i++)
    {
        a = queue[i];
        len[a] = 1;
        for (j = 0; j < n; j++)
            if (graph[j][a] == 1 && len[j] + 1 > len[a])
                len[a] = len[j] + 1;
        if ((5))
            ans = len[a];
    }
    cout << ans << endl;
    return 0;
}

第 1 空应填（ ）

答案

degree[b]++

题解

考点定位

本题（完善程序「DAG 最长路径」第①空）考「入度统计」,对应大纲 4.3.3 拓扑排序（难度【3】）。

程序思路：拓扑排序后按拓扑序 DP：len[v]=max(len[u]+1)。

解题过程

①处读边时累计入度：

``cpp degree[b]++; ``

答案：degree[b]++。

易错提醒

① Kahn 算法：入度 0 的点先入队；② 每条边 b 端入度 +1。