Pagini recente » Cod sursa (job #1568068) | Cod sursa (job #2155663) | Cod sursa (job #1258998) | Cod sursa (job #582487) | Cod sursa (job #681540)
Cod sursa(job #681540)
Program Depth_First_descompun_in_comp_conexe;
type natural = 0..1;
var fi,fo : text;
n,i,j,nrc,q,m : longint;
a:array[0..6000,0..6000] of natural;
suc,pred:array[0..6000] of longint;
Procedure df_r1(nod:longint);
var k:longint;
begin
suc[nod]:=nrc;
for k:=1 to n do if (suc[k]=0) and (a[nod,k]=1) then df_r1(k);
end;
Procedure df_r2(nod:longint);
var k:longint;
begin
pred[nod]:=nrc;
for k:=1 to n do if (pred[k]=0) and (a[k,nod]=1) then df_r2(k);
end;
begin
assign(fi,'ctc4.in'); reset(fi); readln(fi,n,m); nrc:=0;
assign(fo,'ctc.out'); rewrite(fo);
for q:=1 to m do begin
readln(fi,i,j);
a[i,j]:=1;
end;
for i:=1 to n do begin suc[i]:=0; pred[i]:=0; end;
for i:=1 to n do if suc[i]=0 then begin
nrc:=nrc+1;
df_r1(i); df_r2(i);
for j:=1 to n do if suc[j]<>pred[j] then begin
suc[j]:=0;
pred[j]:=0;
end;
end;
writeln(fo,nrc);
for i:=1 to nrc do begin
for j:=1 to n do if suc[j]=i then write(fo,j,' ');
writeln(fo);
end;
close(fi); close(fo);
end.