Графы в ЕГЭ

В9. Поиск путей в графе

Составим программу для решения задания В9.
На рисунке - схема дорог, связывающая города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует путей из города А в город К?

Схема дорог представляет из себя орграф. Построим для него матрицу смежности и сохраним её в текстовом файле inB9.txt. 

0 1 1 1 0 0 0 0 0

0 0 0 1 1 0 0 0 0

0 0 0 1 0 1 0 0 0

0 0 0 0 1 0 1 0 0

0 0 0 0 0 0 0 1 1

0 0 0 0 0 0 1 0 1

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0

Для корректной работы программы пронумеруем вершины таким образом, чтобы направления были заданы от вершины с меньшим номером к вершине с большим. Полученная матрица смежности несимметрична.

const N=9;

var graph: array [1..N, 1..N] of integer;  // массив для определения графа

    R: array [1..N] of integer;//массив количества путей

    f:text; i,j,k:integer;

begin

  assign(f,'inB9.txt');

  reset(f);

  for i:= 1 to N  do

    begin

      for j:=1 to N do read(f,graph[i,j]);

      readln(f);

    end;

  close(f);

  for i:= 1 to N  do R[i]:=0;

  R[1]:=1;

  for i:= 1 to N  do

     for j:=1 to N do

        if graph[i,j]=1 then R[j]:=R[j]+R[i];

     for k:= 1 to N  do write(R[k],' ');

  writeln;

end.