强连通分量怎么写( 二 ) _连通

3.请问如何求（有向/无向）图的强连通分量,还有,基础一点,怎么求有求强连通分量的算法有tarjan和kosaraju 两种算法
相较之下 tarjan写起来比较简单 Kosaraju比较麻烦
但是想起来 Kosaraju比较简单
其他求强连通分量的算法要是还有的话估计就是需要更高深的数据结构的算法了
建议还是学下tarjan 因为他可以帮你做很多事比如求桥求割点缩环而且写起来也很简单
连通图的求法可以直接DFS 每次DFS到一个点就把它记录成已到达然后继续向下搜索每次DFS就可以求出一个连通图
附上tarjan的代码
var
【强连通分量怎么写】next,head,point:array[1..1000] of longint;
time,tot,i,j,n,m,x,y,t:longint;
v:array[1..10000] of byte;
f,z,q:array[1..1000] of longint;
low,rea:array[1..10000] of longint;
function min(x,y:longint):longint;
begin
if xend;
procedure add(x,y:longint);
begin
inc(tot);
next[tot]:=head[x];
head[x]:=tot;
point[tot]:=y;
end;
procedure dfs(x:Longint);
var
i,j:longint;
begin
inc(time);
low[x]:=time;
rea[x]:=time;
v[x]:=1;
inc(t);
z[t]:=x;
j:=head[x];
while j0 do
begin
if v[point[j]]=0 then dfs(point[j]);
if v[point[j]]j:=next[j];
end;
if low[x]=rea[x] then
begin
inc(tot);
while z[t+1]x do
begin
inc(q[tot]);
f[z[t]]:=tot;
v[z[t]]:=2;
dec(t);
end;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
add(x,y);
end;
tot:=0; time:=0;
for i:=1 to n do
if v[i]=0 then dfs(i);
//writeln(tot);
for i:=1 to n do
if q[f[i]]1 then writeln('T') else writeln('F');
end.

文章插图