(最长路径)给定一个有向无环图,每条边长度为 ,求图中的最长路径长度。(第五空 2 分,其余 3 分)
输入:第一行是结点数 (不超过 )和边数 ,接下来 行,每行两个整数 ,表示从结点 到结点 有一条有向边。结点标号从 到 。 输出:最长路径长度。
提示:先进行拓扑排序,然后按照拓扑序计算最长路径。
#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 空应填( )
第 2 空应填( )
第 3 空应填( )
第 4 空应填( )
第 5 空应填( )