【模板】Tarjan求强连通分量/求割点/求割边
codesonic
2018-02-05 17:29:43
# 强连通分量
先下几个定义：
强连通：在一个有向图G中，节点a可以到达节点b，节点b也可以到达节点a，则这两个节点强连通
强连通图：在一个有向图G中，任意两个节点都能互相到达，则这个图是强连通图
强连通分量：在一个有向图G中，有子图满足每2个点都强连通，则这个子图是强连通分量
只有一个节点的图为强连通图。
拿一张在全网满天飞的图做样例：
图中{1,3,4,2}、{5}、{6}分别为一个强连通分量
即：
上图由红线框起来的为强连通分量
---
Tarjan是基于DFS的算法，利用DFS构造一个搜索树，每个强连通分量为搜索树上的一个子树。搜索时把每个节点~~扔~~压进一个一个栈，回溯时判定。
对节点i定义两个数组元素，DFN[i]和LOW[i]，分别表示节点i是第几个被搜索到的节点，LOW[i]为节点i或节点i的子树能回溯到的最早的栈中节点的DFN
则
LOW[i]=min(DFN[i],所有LOW[j]（i为j的父节点）,DFN[j]（j为i的父节点且j在栈中）)
显然如果DFN[i]=LOW[i]，则i为目前搜索树的根
给段伪代码吧，结合代码理解LOW[i]的赋值
```cpp
void tarjan(int i) {
搜索次序编号自增1
DFN[i]=LOW[i]=搜索次序编号;
将i压入栈;
for(对i的每条出边) {
定义j为遍历到的出边的终点
if (j没有被搜索过) {
搜索j;
LOW[i]=min(LOW[i],LOW[j]);
}
else if(j在栈中)
LOW[i]=min(LOW[i],DFN[j]);
}
if (i为目前搜索树的根) {
将所有以i为祖先的栈中节点出栈
}
}
```
和其他的blog一样，对下面这张图演示一下tarjan算法的流程
搜索第一个节点：
DFN[1]=LOW[1]=1,1入栈
因为3没有被搜索过，所以3入栈，搜索3，再对5遍历，5仍没有被搜索过，搜索5，接着搜索6，此时栈的情况如下图：
且DFN[1]=1,DFN[3]=2,DFN[5]=3,DFN[6]=4,LOW[6]=4,发现6没有出边，开始退栈，仅退了6一个节点，所以{6}为一个强连通分量，返回5的搜索，同理把5退栈,{5}为一个强连通分量
返回节点3的搜索，遍历了节点4,DFN[4]=5，发现节点4有出边去1,1在栈中且1的的DFN为1，所以LOW[4]=1,继续搜索节点4，发现节点4有边连向6，但6不在栈内且6已经被搜索过，不管。返回节点3的搜索
节点3搜索结束，返回节点1的搜索
节点1有出边到达2，搜索节点2,DFN[2]=6，节点2有出边到4，4已经搜索过但，4在栈中，LOW[2]=DFN[4]=5,返回节点1的搜索
发现节点DFN[1]=LOW[1],退栈，取出了栈中所有节点，得出最后一个强连通分量{1,3,4,2}
搜索至此结束
但是如果这个图G不联通呢？
很简单，在主函数调用tarjan的地方加个for就行了：
```cpp
for(int i=1;i<=n;i++)
if(!DFN[i])
tarjan(i);
```
好像也没有全裸的模版题，比较裸的只能给出这个了[P2835](https://www.luogu.org/problemnew/show/P2835)
以下是该题代码，链式前向星存图：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=10010,M=50010;
int n;
int tot=0,head[M],head2[M],head3[M],cnt,Index,top;//cnt是强连通分量的个数，Index是是搜索次序编号，head2，head3计数用
int DFN[N],LOW[N],stap[N],which[N];//stap是栈，which表示该节点位于哪一个强连通分量，
bool flag[N][N];
bool instack[N];
struct edge {
int u,v,next;
} G[M];
void add_edge(int u,int v) {
G[++tot].u=u;
G[tot].v=v;
G[tot].next=head[u];
head[u]=tot;
}
void tarjan(int i) {
DFN[i]=LOW[i]=++Index;
instack[i]=true;
stap[++top]=i;
for (int e=head[i]; e; e=G[e].next) {
int j=G[e].v;
if (!DFN[j]) {
tarjan(j);
LOW[i]=min(LOW[i],LOW[j]);
}
else if(instack[j])
LOW[i]=min(LOW[i],DFN[j]);
}
int x;
if (DFN[i]==LOW[i]) {
cnt++;
do {
x=stap[top--];
instack[x]=false;
which[x]=cnt;
} while (x!=i);
}
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
while(1) {
int x;
scanf("%d",&x);
if(!x) break;
add_edge(i,x);
}
}
for(int i=1; i<=n; i++)
if(!DFN[i])
tarjan(i);
for(int i=1; i<=n; i++) {
for(int j=head[i]; j; j=G[j].next) {
if(which[i]!=which[G[j].v]) {
head2[which[i]]++;
head3[which[G[j].v]]++;
}
}
}
int num=0;
for(int i=1; i<=cnt; i++) {
if(!head3[i])
num++;
}
printf("%d\n",num);
return 0;
}
```
分析一下时间复杂度
其中tarjan函数显然要遍历每一条边和每一个点的时间复杂度是O（n+m）
以下的代码并没有产生更多的时间复杂度，因为它仅对没有搜索过的点进行搜索
```cpp
for(int i=1; i<=n; i++)
if(!DFN[i])
tarjan(i);
```
---
---
---
# 割点
割点也是可以用tarjan算法求的~~（tarjan老爷子你到底发明了多少算法）~~
在求割点的代码中，DFN和LOW的含义一样，可以不用多说，主要要写的是割点的定义和如何求。
先引入概念“双联通分量”，双联通分量的定义为：
在一个双联通分量中，删去任何一个点（即删除它与连接着它的所有边）之后这个分量仍然强连通
割点的定义为：
在一个强连通分量中，删去了某一个点之后这个强连通分量不再强连通，则称这个点为割点。
显然双联通分量是没有割点的
割点的判断方法如下（可以尝试证明）：
如果这个点u是搜索树的树根，且它的子树数量大于或等于二，那么u为割点；
如果有一条边(u,v),其中u在搜索树中是v的父亲，且DFN(u)<=LOW(v)，则点u为割点。
那么代码很显然了。
例题：[P3388](https://www.luogu.org/problemnew/show/P3388)
代码如下：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000010,M=1000010;
int n,m;
int tot=0,head[M],head2[M],head3[M],cnt,Index,top;
int DFN[N],LOW[N];
bool is[N];
bool instack[N];
struct edge {
int u,v,next;
} G[M];
void add_edge(int u,int v) {
G[++tot].u=u;
G[tot].v=v;
G[tot].next=head[u];
head[u]=tot;
}
void tarjan(int u,int fa) {
int son=0;
DFN[u]=LOW[u]=++Index;
for (int i=head[u]; i; i=G[i].next) {
int v=G[i].v;
if(!DFN[v]) {
tarjan(v,fa);
LOW[u]=min(LOW[u],LOW[v]);//定义
if(u==fa) son++;
else if(LOW[v]>=DFN[u]) is[u]=1;
}
LOW[u]=min(LOW[u],DFN[v]);
}
if(son>=2) is[u]=1;
}
int main() {
scanf("%d%d",&n, &m);
for(int i=1; i<=m; i++) {
int x,y;
scanf("%d%d",&x,&y);
add_edge(y,x);
add_edge(x,y);
}
for(int i=1; i<=n; i++)
if(!DFN[i])
tarjan(i,i);
int ans=0;
for (int i=1; i<=n; i++)
if(is[i])
ans++;
printf("%d\n",ans);
for(int i=1; i<=n; i++)
if(is[i])
printf("%d ",i);
return 0;
}
```
# 割边（桥）
桥其实就是割边
我们还是利用low和dfn的性质作文章
~~（其实这些东西没几个人会证）~~
对于一条边（u，v），若满足$LOW[v]>DFN[u]$，那么这条边是割边
这个时候我们悲惨地发现，会发生重边
那么我们怎么处理呢？
我们直接在给边多维护一个值，加边的时候判断有没有重边就行了
于是addedge函数变成了这样：
```cpp
void add_edge(int u,int v,int id) {
for(int i=head[u];i;i=G[i].next)
{
if(G[i].v==v)
{
G[i].mul=true;
return;
}
}//找重边
G[tot].id=id;
G[tot].v=v;
G[tot].next=head[u];
head[u]=tot++;
G[tot].id=id;
G[tot].v=u;
G[tot].next=head[v];
head[v]=tot++;
}
```
（因为是无向图要存两次边，无法确认边的id，对每一条边引入了新的一个变量id）
tarjan函数也差不离：
```cpp
void tarjan(int u,int fa) {
DFN[u]=LOW[u]=++Index;
for (int i=head[u]; i; i=G[i].next) {
int v=G[i].v;
if(!DFN[v]){
tarjan(v,u);
LOW[u]=min(LOW[u],LOW[v]);
if(LOW[v]>DFN[u]&&!G[i].mul)
is[G[i].id]=1;
}
else if(v!=fa)
LOW[u]=min(LOW[u],DFN[v]);
}
}
```
（其中v!=fa是因为不是父亲边才更新LOW）
因为没有例题所以自己创了一道私题：
[割点](https://www.luogu.org/problemnew/show/U22159)