【学习整理】Tarjan：强连通分量+割点+割边

Tarjan求强连通分量

在一个有向图中，如果某两点间都有互相到达的路径，那么称中两个点强联通，如果任意两点都强联通，那么称这个图为强联通图；一个有向图的极大强联通子图称为强联通分量。

$Tarjan$ 算法可以在 $O(n+m)$ 的时间内求出一个图的所有强联通分量。

$dfn(i)$ 表示进入结点 $i$ 的时间

$low(i)$ 表示从 $i$ 所能追溯到的栈中点的最早时间

如果某个点 $x$ 已经在栈中则更新 $low[i]=min(low[i],dfn[x]);$

否则对 $x$ 进行回溯，并在回溯后更新 $low[i]=min(low[i],low[x]);$

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<stack>

using namespace std;

int n,m,tot,ind,ans;

int dfn[200005],low[200005],last[200005];

bool ins[200005];

stack<int> s;

struct hh

{

    int fr,to,next;

}e[500005];

void add(int fr,int to)

{

    e[++tot].to=to;e[tot].fr=fr;

    e[tot].next=last[fr];

    last[fr]=tot;

}

void tarjan(int now)

{

    int i,j;

    s.push(now);

    ins[now]=true;

    low[now]=dfn[now]=++dex;

    for(i=last[now];i;i=e[i].next)

        if(!dfn[e[i].to])

        {

            tarjan(e[i].to);

            low[now]=min(low[now],low[e[i].to]);

        }

        else if(ins[e[i].to])low[now]=min(low[now],dfn[e[i].to]);

    if(dfn[now]==low[now])

    {

        cnt=0;

        do

        {

            j=s.top();s.pop();

            ins[j]=false;

            cnt++;

        }while(j!=now);

        ans=max(ans,cnt);

    }

}

int main()

{

    int i,j,u,v;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)

    {

        scanf("%d%d",&u,&v);

        add(u,v);

    }

    for(i=1;i<=n;i++)

        if(!dfn[i]) tarjan(i);

    printf("%d",ans);

    return 0;

}

Tarjan求割点

在一个无向图中，如果删掉点 $x$ 后图的连通块数量增加，则称点 $x$ 为图的割点。

对于搜索树上的非根结点 $x$ ，如果存在子节点 $i$ 满足 $low[i]$\geq$dfn[x]$ ，即 $i$ 向上无法达到 $x$ 的祖先，则 $x$ 为割点。

对于搜索树上的根节点 $x$ ，若它的子节点数 $\geq2$ ，则 $x$ 为割点。

void tarjan(int x,int fa)

{

    int i,j;

    dfn[x]=low[x]=++dex;

    for(i=last[x];i;i=e[i].next)

    {

        ++t[x];

        if(!dfn[e[i].to])

        {

            tarjan(e[i].to,x);

            low[x]=min(low[x],low[e[i].to]);

            if(x==root&&t[x]>=2) opt[x]=true;

            else if(x!=root&&low[e[i].to]>=dfn[x]) opt[x]=true;

        }

        else if(e[i].to!=fa) low[x]=min(low[x],dfn[e[i].to]);

    }

}

Tarjan求割边

对于当前结点 $x$ ，若邻接点中存在结点 $y$ 满足 $low[y]$\textgreater$dfn[x]$ ，则 $(x,y)$ 为割边。

void tarjan(int x,int fa)

{

    int i,j;

    low[x]=dfn[x]=++dex;

    for(i=last[x];i;i=e[i].next)

        if(e[i].to!=fa)

        {

            if(dfn[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);

            else

            {

                tarjan(e[i].to,x);

                low[x]=min(low[x],low[e[i].to]);

                if(low[e[i].to]>dfn[x]) opt[e[i].id]=true;

            }

        }

}

巴特西

【学习整理】Tarjan：强连通分量+割点+割边

最新文章

热门文章