{
求有向圖的強連通分支，用鄰接表實現圖
                By starfish
           starfish.h@china.com

運行實例如下（圖的輸入格式為 u ,v ,邊權）：
Please input nodes count:8
Please input sides count:14
Please input Graph:
1 2 1
2 3 1
3 4 1
4 3 1
2 6 1
5 6 1
2 5 1
5 1 1
6 7 1
7 6 1
3 7 1
7 8 1
8 8 1
4 8 1
The strongly connected componets of the graph are:
1 5 2
3 4
6 7
8
}

program Strongly_Connected_Components;
const
MaxNodeCount=50;  {圖的最大節點數目}

type
PNode=^TNode;
TNode=record
        vertex:integer;    {相鄰頂點標號}
        SideInfo:integer;  {邊的信息}
        next:PNode;        {下一個相鄰頂點} 
      end;
TGraph=record  {用鄰接表定義圖}
         size:integer;  {圖的結點個數}
         adjList:array [1..MaxNodeCount] of PNode;            
       end;  

var
G:TGraph;

procedure AddSide(var G:TGraph;u,v,w:integer);   {增加一條邊}
var
p:PNode;
begin
new(p);
p^.vertex:=v;
p^.SideInfo:=w;
p^.next:=G.adjList[u];
G.adjList[u]:=p;
end;

procedure CreateGraph(var G:TGraph);
var
i,m,u,v,w:integer;
begin
write('Please input the node count:');readln(G.size);
if G.size>MaxNodeCount then 
 begin
  writeln('Error! Node count must <= ',MaxNodeCount,' !');
  halt;
 end;
for i:=1 to G.size do  {初始化圖G}
  G.adjList[i]:=nil;
write('Please input sides count:');readln(m); {讀入邊的數目}
writeln('Please input Graph:');
for i:=1 to m do     {用鄰接表方式讀入圖}
 begin
   readln(u,v,w);
   AddSide(G,u,v,w);   {增加一條邊}
 end;   
end;


procedure transposition(Var G1,G2:TGraph); {求G1的轉置矩陣放在G2中，復雜度為O(V+E)}
var
i:integer;
p,q:PNode;
begin
G2.size:=G1.size;
for i:=1 to G2.size do
 G2.adjList[i]:=nil;
for i:=1 to G1.size do
 begin
  p:=G1.adjList[i];
  while p<>nil do        {這個while循環對圖G1進行轉置}
   begin
    new(q);
    q^.vertex:=i;
    q^.SideInfo:=p^.SideInfo;
    q^.next:=G2.adjList[p^.vertex];
    G2.adjList[p^.vertex]:=q;
    p:=p^.next;   
   end; 
 end; 
end;


procedure Strongly_Connect(var G1:TGraph); {求有向圖的強連通分支}
var
G2:TGraph;
visited:array[1..MaxNodeCount] of boolean;
ft:array [1..MaxNodeCount] of integer; {ft[i]記錄在時刻i完成的節點標號}
time,i:integer;

procedure DFS_Search_1(var G:TGraph;v:integer);
var
p:PNode;
begin
visited[v]:=true;
p:=G.adjList[v];
while p<>nil do
 begin
  if (not visited[p^.vertex]) then DFS_Search_1(G,p^.vertex);
  p:=p^.next;
 end;
inc(time); 
ft[time]:=v; 
end;

procedure DFS_Search_2(var G:TGraph;v:integer);
var
p:PNode;
begin
visited[v]:=true;
write(v,' '); {打印當前訪問的節點}
p:=G.adjList[v];
while p<>nil do
 begin
  if (not visited[p^.vertex]) then DFS_Search_2(G,p^.vertex);
  p:=p^.next; 
 end;
end;


begin
for i:=1 to G1.size do visited[i]:=false;
time:=0;
for i:=1 to G1.size do
 if not visited[i] then
    DFS_Search_1(G1,i);   {深度優先遍歷G1，并且記錄每個節點的完成時刻}
    
transposition(G1,G2);  {求G1的轉置圖G2}

for i:=1 to G2.size do visited[i]:=false;  

writeln('The strongly connected componets of the graph are:');

for i:=G2.size downto 1 do      {按照深度優先遍歷G1時每個節點的完成時刻遞減順序}
 if not visited[ ft[i] ] then
  begin
   DFS_Search_2(G2,ft[i]);
   writeln; 
  end;  
end;



begin
CreateGraph(G);
Strongly_Connect(G);
end.