接上一篇

我真是傻乎乎的

割点割边强连通分量是T算法在无向图和有向图中的两个应用啦,而且上一篇我的问题就是建立在无知上的!

下面是强连通分量,的几行核心代码

if( !dfn[v] )//没标记
    low[u] = min( low[u], low[v] );
else if (!co[v])//标记了,且未出栈
    low[u] = min( low[u], dfn[v] );
//或low[u] = min( low[u], low[v] );

两个都写成low(u)=min{low(u),low(v)}是可以的!

还用前天那张手绘图吧!(我实在不会在电脑上画图,觉得特别麻烦,有木有大佬教教我!!!)

这是有向图

这张图有两个强连通分量{12345}{6}

在强中,low5是可以等于1的(low[u]=min(low[u],low[v]);),low5也可以等于3(low[u]=min(low[u],dfn[v]);),不管他等于什么,只要不等于自己,就可以啦(就能说明他不是一个强连通分量的头头)

而在割点中,low5是绝对不能等于1的!!(经过父)


割点割边强连通分量是T算法在无向图和有向图中的两个应用。割点割边,强连通分量有区别,所以程序也会不一样啦!不过差不多意思是差不多的(病句?),都是深搜,有时间戳,不同的是low的求法和判断是不是割或强!

好啦,最后附上前天傻乎乎随笔的链接https://www.cnblogs.com/xfff/p/13491267.html

原文地址:https://www.cnblogs.com/xfff/p/13502793.html