组合题5 个小题
已作答 0 / 5
(最长路径)给定一个有向无环图,每条边长度为 1,求图中的最长路径长度。(第五空 2 分,其余 3 分)
输入:第一行是结点数 n(不超过 100)和边数 m,接下来 m 行,每行两个整数 a,b,表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到 (n−1)。 输出:最长路径长度。
提示:先进行拓扑排序,然后按照拓扑序计算最长路径。
1#include <iostream>2using namespace std;3int n, m, i, j, a, b, head, tail, ans;4int graph[100][100]; // 用邻接矩阵存储图5int degree[100]; // 记录每个结点的入度6int len[100]; // 记录以各结点为终点的最长路径长度7int queue[100]; // 存放拓扑排序结果8int main()9{10 cin >> n >> m;11 for (i = 0; i < n; i++)12 for (j = 0; j < n; j++)13 graph[i][j] = 0;14 for (i = 0; i < n; i++)15 degree[i] = 0;16 for (i = 0; i < m; i++)17 {18 cin >> a >> b;19 graph[a][b] = 1;20 (1);21 }22 tail = 0;23 for (i = 0; i < n; i++)24 if ((2))25 {26 queue[tail] = i;27 tail++;28 }29 head = 0;30 while (tail < n - 1)31 {32 for (i = 0; i < n; i++)33 if (graph[queue[head]][i] == 1)34 {35 (3);36 if (degree[i] == 0)37 {38 queue[tail] = i;39 tail++;40 }41 }42 (4);43 }44 ans = 0;45 for (i = 0; i < n; i++)46 {47 a = queue[i];48 len[a] = 1;49 for (j = 0; j < n; j++)50 if (graph[j][a] == 1 && len[j] + 1 > len[a])51 len[a] = len[j] + 1;52 if ((5))53 ans = len[a];54 }55 cout << ans << endl;56 return 0;57}第 2 空应填( )