4. 【NOIP2017】最长路径

给定一个有向无环图，每条边长度为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;
        ① ;
    }
    
    // 拓扑排序：将入度为0的结点入队
    tail=0;
    for(i=0;i<n;i++)
        if(②) {
            queue[tail]=i;
            tail++;
        }
    
    // 拓扑排序过程
    head=0;
    while(head<tail) {
        for(i=0;i<n;i++)
            if(graph[queue[head]][i]==1) {
                ③ ;
                if(degree[i]==0) {
                    queue[tail]=i;
                    tail++;
                }
            }
        ④ ;
    }
    
    // 计算最长路径
    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(⑤)
            ans=len[a];
    }
    cout<<ans<<endl;
    return 0;
}

选择题：

1. ①处应填（ ）
   {{ select(1) }}

• graph[b][a]=1
• degree[b]=degree[b]+1
• degree[b]=degree[a]+1
• graph[b][a]=graph[a][b]+1

2. ②处应填（ ）
   {{ select(2) }}

• graph[1][i]!=0
• graph[1][i]==0
• degree[i]==0
• degree[i]!=0

3. ③处应填（ ）
   {{ select(3) }}

• degree[i]--
• head++
• tail--
• tail++

4. ④处应填（ ）
   {{ select(4) }}

• graph[queue[head]][i]++
• tail-head
• graph[queue[tail]][i]==1
• head++

5. ⑤处应填（ ）
   {{ select(5) }}

• ans+i<len[a]
• ans<len[a]
• len[a]-1>=ans
• !ans