Strongly Connected Components
Strongly Connected Components
DFS(v)
StartTime := StartTime + 1;
d[v] := StartTime;
low[v] := d[v]; rm[v] := False;
for each w adjacent to v do
if d[w] = 0 then
DFS(w);
low[v]:=min(low[v],low[w]);
else
if not rm[w] then
low[v] :=min(d[w],low[v]);
end
endif
endfor;
if low[v] = d[v] then
rm[v]:= True; Output v;
while SC nonempty and
d[Top(SC)] > d[v] do
output Top(SC);
rm[Top(SC)] := True;
Pop SC;
endwhile;
else
Push v onto SC;
endif
end DFS
for v:= 1 to n do d[v] := 0;
StartTime := 0;
for v:= 1 to n do
if d[v] = 0 then DFS(v);
endfor