【算法-图论-强连通分量】强连通分量和tarjan算法

由 联环己烷 发布

强连通分量

我们刚才学了拓扑排序,现在来看这样一道题:

poj2186 受欢迎的牛

给一张有向图,问有多少节点满足其他所有节点都能到达它。$(n \leq 10000)$

提问:如果本题没有环,要怎么做?

显然,一个点如果存在出度,那么它肯定不满足条件(因为它可达的节点一定可达它)。那么只要数一数有多少个节点存在出度,若只有1个,答案是1,否则是0。

那么在有环的图里咋做呢?就要用到求强连通分量了。

一个强连通分量即一张图上若干个彼此之间两两可达的点组成的集合。

如果我们把每个强连通分量都缩成一个点,那么这张图将变成一张有向无环图。

Tarjan算法

tarjan算法的思路并不是特别复杂,只需要一点dfs思维即可理解。

首先,从图中某一节点开始dfs,并且记录下经过的每个节点的dfs序dfn。如果把我们dfs过程中经过的点和边记录下来,可以发现整个图构成了一个树(或说树形图),这就被称为dfs树。

对于一个点x,它在dfs树上是有一棵子树的,子树里的点有很多边,有的也会连到子树之外的地方。

  1. 如果边恰好连到了x在dfs树上的祖先或与祖先在同一个强连通分量里的点,那么显然x与其祖先在同一个强连通分量内。
  2. 如果连到了不是祖先的节点y

2-1.要么是dfs过程中未经过的,那么就继续dfs。

2-2.要么是dfs中已经经过了,但不是祖先的,那么x一定不能通过该边找到一个强连通分量。原因:若y子树中有一条边,连到xxy的lca之间的点上(若连到lca之上的点上,yx的祖先在同一个强连通分量内,与条件1重合),那么xy确实在同一个强连通分量内。然而这样的话,x理应在y的子树内,与前提不符。

好,于是我们维护一个值low,表示从x的子树中能找到的符合条件1的边,所到达x祖先节点,dfs序最小的那个祖先的dfs序。维护一个栈,里面的点为“当前节点的祖先和与祖先在一个强连通分量里的点。”

当对一个x进行完处理后,若其dfn值和low值相同,说明它是它所在的强连通分量中dfs序最小的节点(也就是最“祖先”的节点),在栈中将它和它上方的点全部弹出,这些点就在同一个强连通分量上。由于保证了总是在dfs序最小节点处获得整个强连通分量,所以也不会算重。

放上一份代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define RI register int
typedef long long LL;
int read() {
    int q=0,w=1;char ch=' ';
    while((ch!='-')&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') w=-1,ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+(ch-'0'),ch=getchar();
    return q*w;
}
const int N=10005,M=5000005;
int n,m,tot,tim,cnt,top;
int h[N],ne[M],to[M],dfn[N],low[N],in_s[N],stk[N],col[N];


void add_edge(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void tarjan(int x) {
    ++tim,dfn[x]=low[x]=tim,stk[++top]=x,in_s[x]=1;
    for(RI i=h[x];i;i=ne[i]) {
        if(!dfn[to[i]]) tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
        else if(in_s[x]) low[x]=min(low[x],dfn[to[i]]);
    }
    if(low[x]==dfn[x]) {
        ++cnt;
        while(stk[top]!=x) col[stk[top--]]=cnt;
        col[stk[top--]]=cnt;
    }
}

int main()
{
    int x,y;
    n=read(),m=read();
    for(RI i=1;i<=m;++i) x=read(),y=read(),add_edge(x,y);
    for(RI i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    for(RI i=1;i<=n;++i) printf("%d\n",col[i]);
    return 0;
}

习题:洛谷P2812 校园网络


仅有一条评论

  1. 三硝基豆腐
    三硝基豆腐 · 2020-07-29 01:15

    u1s1我是到退役前才学会tarjan的

发表评论


京公网安备 11010802033049号