首页 > 试题广场 >

(最长路径)给定一个有向无环图,每条边长度为 1,求图中的最

[填空题]
(最长路径)给定一个有向无环图,每条边长度为 1,求图中的最长路径长度。(第五空 2 分,其余 3 分)
输入:第一行是结点数 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.

这道题你会答吗?花几分钟告诉大家答案吧!