TJALG - Tìm TPLT mạnh

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
type
  list=^node;
  node=record
        u:longint;
        next:list;
  end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

var
  n,m,i,u,v,top:longint;
  low,num,stack,father:array[1..10111] of longint;
  ke:array[1..10111] of list;
  erased:array[1..10111] of boolean;
  cnt,res:longint;

procedure dfs(u:longint);
    var
      v:longint;
      p:list;
    begin
      inc(cnt); low[u]:=cnt; num[u]:=cnt;
      inc(top); stack[top]:=u;
      p:=ke[u];
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if erased[v] then continue;
          if v=father[u] then continue;
          if num[v]=0 then
            begin
              father[v]:=u;
              dfs(v);
              low[u]:=min(low[u],low[v]);
            end
          else low[u]:=min(low[u],num[v]);
        end;

      if low[u]=num[u] then
        begin
          inc(res);
          repeat
            v:=stack[top]; dec(top);
            erased[v]:=true;
          until u=v;
        end;
    end;

begin
  read(n,m);
  for i:=1 to m do
    begin
      read(u,v);
      add(v,ke[u]);
    end;

  fillchar(erased,sizeof(erased),false);
  for i:=1 to n do
    if num[i]=0 then
      begin
        cnt:=0;
        dfs(i);
      end;

  writeln(res);
end.

Download