Pagini recente » Cod sursa (job #2328819) | Cod sursa (job #1185710) | Cod sursa (job #1522008) | Cod sursa (job #2563793) | Cod sursa (job #408582)
Cod sursa(job #408582)
{DINH QUANG DAT TIN 07-10}
{CTC}
CONST
TFI='ctc.in';
TFO='ctc.out';
MAX=100001;
TYPE
arr1int=array[0..MAX] of longint;
pnode = ^node;
node = record
v:longint;
next:pnode;
end;
VAR
fi,fo:text;
cnt,top,k,mm,m,n:longint;
ke:array[0..MAX] of pnode;
d,st,low,num,stack:arr1int;
free:array[0..MAX] of boolean;
PROCEDURE add(u,v:longint);
var
t:pnode;
begin
new(t);
t^.v:=v;
t^.next:=ke[u];
ke[u]:=t;
end;
PROCEDURE input;
var
i,u,v:longint;
begin
assign(fi,tfi);reset(fi);
read(fi,n,m);
for i:= 1 to m do
begin
read(fi,u,v);
add(u,v);
end;
close(fi);
end;
PROCEDURE init;
begin
fillchar(free,sizeof(free),true);
end;
PROCEDURE push(u:longint);
begin
inc(top);
stack[top]:=u;
end;
PROCEDURE dfs(u:longint);
var
v:longint;
t:pnode;
begin
t:=ke[u];
inc(cnt);
low[u]:=cnt;
num[u]:=cnt;
push(u);
while t<>nil do
begin
v:=t^.v;
t:=t^.next;
if free[v] then
begin
if num[v]=0 then
begin
dfs(v);
if low[u]>low[v] then low[u]:=low[v];
end
else if num[v]<low[u] then low[u]:=num[v];
end;
end;
if low[u]=num[u] then
begin
inc(mm);
st[mm]:=k+1;
v:=0;
while u<>v do
begin
v:=stack[top];
dec(top);
inc(k);
d[k]:=v;
free[v]:=false;
end;
end;
end;
PROCEDURE process;
var
i:longint;
begin
for i:= 1 to n do
if num[i]=0 then dfs(i);
st[mm+1]:=n+1;
end;
PROCEDURE output;
var
i,j:longint;
begin
assign(fo,tfo);rewrite(fo);
writeln(fo,mm);
for i:= 1 to mm do
begin
for j:= st[i] to st[i+1]-1 do
write(fo,d[j],' ');
writeln(fo);
end;
close(fo);
end;
BEGIN
input;
init;
process;
output;
END.