1.强连通分量是什么

强连通分量指的是部分点的集合如果能够互相到达(例如 1→3,3→2,2→1(有向图)这种,132每个点都能互相抵达)

或者说,有一个环,环上点的集合就是一个强连通分量

2.那怎么实现呢?

1.根据这个定义,容易想到的就是枚举每个环,虽然确可以得到环,但是时间复杂度趋近于O(n^3)[复杂度自己算的可能不准确]

2.优化:类似于SPFA,当每个点的入度小于进队次数的时候,跳出,外加一个数组存当前点的来源

3.O(n^2+m)算法 得到每个点的遍历序,然后反向遍历,有交集的部分就是一个强连通分量

4.O(n+m)算法 : tarjan,kosaraju (貌似还有一个算法和tarjan有异曲同工之妙)

前两种应该好写但是没必要写,真的有用的就是tarjan和kos算法,但是kos是跑的两遍bfs,常数比较大,所以学了tarjan

tarjan 学习记-LMLPHP

比如这张图,求他的强连通分量个数

    low[u]=++ds;
dfn[u]=low[u];
s.push(u);
int i,j;
ins[u]=;
for(i=head[u];i;i=e[i].next)
{
j=e[i].to;
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(ins[j]) low[u]=min(low[u],dfn[j]);
}

首先找到一个没有被访问的点(比如1)

然后从1开始遍历,dfn[i]不仅标记了i是否被访问[0或者有值],同时标记这个点被访问的序号(留着日后作对比),右边绿色的是当前栈的情况

low表示从该店遍历能够找到的最小被访问的序号,如果往下没有边的话dfn[i]=low[i]

tarjan 学习记-LMLPHP

当现在找到了6这个点不能刷新low,因此不难发现{6}是一个强连通分量

if(dfn[u]==low[u])
{
cnt++;
while(u!=j)
{
j=s.top();
s.pop();
ins[j]=;
bd[j]=cnt;
}
}

tarjan 学习记-LMLPHP

于是6退栈,然后发现u==j 即6==6,跳出,然后重复这样做,发现{5}也是个强连通分量

回到3,发现还没找完边,跳到4,发现4与1联通,又可以得到low[1]]=1回溯发现low[3]=1

tarjan 学习记-LMLPHP

然后走剩下一条边,同理,发现low[1]=low[2]=low[3]=low[4]

if(dfn[u]==low[u])
{
cnt++;
while(u!=j)
{
j=s.top();
s.pop();
ins[j]=;
bd[j]=cnt;
}
}

于是u!=j一直做下去,的到剩下的强连通分量{1,2,3,4}

tarjan 学习记-LMLPHP

对了这道题在我发在洛谷上了:

https://www.luogu.org/problemnew/show/T84034

05-11 13:28