73 lines
1.4 KiB
ObjectPascal
73 lines
1.4 KiB
ObjectPascal
program Kosaraju_SCC;
|
|
{$mode objfpc}{$modeswitch arrayoperators}
|
|
{$j-}{$coperators on}
|
|
type
|
|
TDigraph = array of array of Integer;
|
|
|
|
procedure PrintComponents(const g: TDigraph);
|
|
var
|
|
Visited: array of Boolean = nil;
|
|
RevPostOrder: array of Integer = nil;
|
|
gr: TDigraph = nil; //reversed graph
|
|
Counter, Next: Integer;
|
|
FirstItem: Boolean;
|
|
|
|
procedure Dfs1(aNode: Integer);
|
|
begin
|
|
Visited[aNode] := True;
|
|
for Next in g[aNode] do begin
|
|
gr[Next] += [aNode];
|
|
if not Visited[Next] then
|
|
Dfs1(Next);
|
|
end;
|
|
RevPostOrder[Counter] := aNode;
|
|
Dec(Counter);
|
|
end;
|
|
|
|
procedure Dfs2(aNode: Integer);
|
|
begin
|
|
Visited[aNode] := True;
|
|
for Next in gr[aNode] do
|
|
if not Visited[Next] then
|
|
Dfs2(Next);
|
|
if FirstItem then begin
|
|
FirstItem := False;
|
|
Write(aNode);
|
|
end else
|
|
Write(', ', aNode);
|
|
end;
|
|
|
|
var
|
|
Node: Integer;
|
|
begin
|
|
SetLength(Visited, Length(g));
|
|
SetLength(RevPostOrder, Length(g));
|
|
SetLength(gr, Length(g));
|
|
Counter := High(g);
|
|
for Node := 0 to High(g) do
|
|
if not Visited[Node] then
|
|
Dfs1(Node);
|
|
FillChar(Pointer(Visited)^, Length(Visited), 0);
|
|
for Node in RevPostOrder do
|
|
if not Visited[Node] then begin
|
|
FirstItem := True;
|
|
Write('[');
|
|
Dfs2(Node);
|
|
WriteLn(']');
|
|
end;
|
|
end;
|
|
|
|
const
|
|
g: TDigraph = (
|
|
(1),
|
|
(2),
|
|
(0),
|
|
(1, 2, 4),
|
|
(3, 5),
|
|
(2, 6),
|
|
(5),
|
|
(4, 6, 7)
|
|
);
|
|
begin
|
|
PrintComponents(g);
|
|
end.
|