输入:第一行是结点数 n(不超过 100)和边数 m,接下来 m 行,每行两个整数a,b,表示从结点 a 到结点b 有一条有向边。结点标号从 0 到(n-1)。
输出:最长路径长度。
提示:先进行拓扑排序,然后按照拓扑序计算最长路径。
var n, m, i, j, a, b, head, tail, ans : longint; graph : array[0..100, 0..100] of longint; // 用邻接矩阵存储图 len, queue, degree : array[0..100] of longint; // len[]记录以各结点为终点的最长路径长度 // queue[]存放拓扑排序结果 // degree[]记录每个结点的入度 begin read(n, m); for i := 0 to n - 1 do for j := 0 to n - 1 do graph[i][j] := 0; for i := 0 to n - 1 do degree[i] := 0; for i := 0 to m - 1 do begin read(a, b); graph[a][b] := 1; 1; end; tail := 0; for i := 0 to n - 1 do if (2) then begin queue[tail] := i; tail := tail + 1; end; head := 0; while (tail < n - 1) do begin for i := 0 to n - 1 do if (graph[queue[head]][i] = 1) then begin 3; if (degree[i] = 0) then begin queue[tail] := i; tail := tail + 1; end; end; 4; end; ans := 0; for i := 0 to n - 1 do begin a := queue[i]; len[a] := 1; for j := 0 to n - 1 do if (graph[j][a] = 1) and (len[j] + 1 > len[a]) then len[a] := len[j] + 1; if (5) then ans := len[a]; end; writeln(ans); end.