Đồ thị – #2 BFS

const 
    maxN = 100;
    fi = 'graph.inp';
var 
    a: array[1..maxN, 1..maxN] of longint;
    n, m, s, t: longint;

    avail: array[1..maxN] of boolean;
    trace: array[1..maxN] of longint;

    queue: array[1..maxN*maxN] of longint;
    front, rear: longint;

procedure ReadFile;
var 
    f: text;
    i, u, v: longint;
begin
    assign(f, fi);
    reset(f);
    readln(f, n, m, s, t);
    writeln(n, ' ', m, ' ', s, ' ' , t);

    fillchar(a, sizeof(a), 0);
    fillchar(avail, sizeof(avail), True);
    fillchar(trace, sizeof(trace), 0);

    for i := 1 to m do 
        begin
            readln(f, u, v);
            a[u, v] := 1;
        end;
    close(f);
end;

procedure PrintMat;
var 
    u, v: longint;
begin
    for u := 1 to n do  
        begin
            for v := 1 to n do 
                write(a[u, v]:3);
            writeln;
        end;
end;

procedure Push(v: longint);
begin 
    inc(rear);
    queue[rear] := v;
end;

function Pop: longint;
begin
    Pop := queue[front];
    inc(front);
end;

procedure BFS(s: longint);
var 
    u, v: longint;
begin
    // Init queue
    front := 1;
    queue[front] := s;
    rear := 1;
    avail[s] := False;
    // BFS
    repeat
        u := Pop;
        writeln(u);
        for v := 1 to n do 
            if (a[u, v] = 1) and avail[v] then 
                begin
                    Push(v);
                    avail[v] := False;
                    trace[v] := u;
                end;    
    until front > rear;
end;

procedure Tracing;
var 
    u: longint;
begin
    if trace[t] = 0 then 
        writeln('No path')
    else 
        begin 
            u := t;
            while u <> s do 
                begin 
                    write(u, ' < ');
                    u := trace[u];
                end;
            writeln(s);
        end;
end;

begin 
    ReadFile;
    //PrintMat;
    BFS(s);
    Tracing;
end.