TJALG - Tìm TPLT mạnh

Tác giả: flashmt

Ngôn ngữ: Pascal

uses math;
var n,m,i,j,sm,cnt,last:longint;
    p,st,low,num:array[1..10010] of longint;
    a,b,c:array[1..100010] of longint;
    d:array[1..10010] of boolean;

procedure visit(x:longint);
var i:longint;
begin
     inc(cnt); num[x]:=cnt; low[x]:=cnt;
     inc(last); st[last]:=x;
     for i:=p[x]+1 to p[x+1] do
         if not d[a[i]] then
         begin
              if num[a[i]]>0 then low[x]:=min(low[x],num[a[i]])
              else
              begin
                   visit(a[i]);
                   low[x]:=min(low[x],low[a[i]]);
              end;
         end;
     if low[x]=num[x] then
     begin
          inc(sm);
          repeat
                i:=st[last];
                dec(last);
                d[i]:=true;
          until i=x;
     end;
end;

begin
     read(n,m);
     for i:=1 to m do
     begin
          read(b[i],c[i]);
          inc(p[b[i]]);
     end;
     for i:=2 to n+1 do inc(p[i],p[i-1]);
     for i:=1 to m do
     begin
          a[p[b[i]]]:=c[i];
          dec(p[b[i]]);
     end;
     for i:=1 to n do
         if not d[i] then visit(i);
     writeln(sm);
end.

Download