输入:第一行是结点数 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; }