Раздел «Алгоритмы».StrongConnectivityPAS:

Поиск сильно связанных компонент на Pascal

//(C) Igor Kvasov
const
  maxn = 100;
var
  ne,ne_T,was,list,ans:array[1..maxn]of longint;
  e,e_T:array[1..maxn,1..maxn]of longint;
  i,j,n,m,u,v,nlist,color:longint;

procedure find(i:longint);
var
  j:longint;
begin
  was[i]:=1;
  for j:=1 to ne[i] do if was[e[i,j]]=0 then find(e[i,j]);
  inc(nlist); list[nlist]:=i;
end;

procedure find_T(i:longint);
var
  j:longint;
begin
  was[i]:=1;
  for j:=1 to ne_T[i] do if was[e_T[i,j]]=0 then find_T(e_T[i,j]);
  ans[i]:=color;
end;

begin
  read(n,m);
  for i:=1 to m do begin
    read(u,v);
    inc(ne[u]); e[u,ne[u]]:=v;
    inc(ne_T[v]); e_T[v,ne_T[v]]:=u;
  end;
  for i:=1 to n do if was[i]=0 then find(i);
  fillchar(was,sizeof(was),0);
  for i:=n downto 1 do if was[list[i]]=0 then begin
    inc(color);
    find_T(list[i]);
  end;
  writeln(color);
  for i:=1 to color do begin
    for j:=1 to n do if ans[j]=i then write(j,' ');
    writeln;
  end;
end.

-- IgorKvasov? - 22 Dec 2004

AlgorithmClasifyForm
Type: Код
Scope: Графы
Strategy:  
Complexity: Low