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.