Tarjan求强连通分量


强连通,就是一个有向图中所有点都互相连接,从任意点到达任意点都是可能的,那么称这个图是强连通的。而强连通分量便是在一个图中找到这个图的强连通的子图。

而Tarjan是求强连通分量的利器。

求强连通分量的目的是什么呢……

对于一个有向图,我们可以通过强连通分量得到一个DAG(有向无环图),这种有很优良的性质,能够进行拓扑排序,进行动态规划等等。一般在算法中作为预处理用到。

——选自http://blog.csdn.net/jokes000/article/details/7538994


JDOJ1588,VijosP1626 爱在心中

题目大意:请你在一个有向图中找到强连通分量个数,以及如果一个强连通分量可由除此之外所有点抵达请输出这个强连通分量的组成元素,如没有输出-1.

这道题就是Tarjan裸题……直接跑Tarjan找到所有的强连通分量并记录,第一问完成。第二问这样处理:查找有没有出度为0的强连通分量,如果有1个则为第二问答案,如果没有或有两个以上则输出-1.

如何证明?我们假设这个强连通分量有一个出边指向外围的一个点。如果指回来,那么这个点也应包含在这个强连通分量里,那么这个点一定没有一条边指回来。所以这个点就不能抵达这个强连通分量。如果有两个以上的话那么其中一个因为没有出边就连接不到另一个出度=0的强连通分量了。所以得证。

附AC代码。

#include <cstdio>
#include <algorithm>
 
int temp,res[1100],fa[1100],top,tot,cnt,n,m,inx,iny,to[10100],next[10100],head[1100],st[1100],deep[1100],low[1100],f[1100][1100],ans;
bool flg,use[1100],ins[1100];
 
void tarjan(int target)
{
    st[++top]=target;
    use[target]=true;
    ins[target]=true;
    deep[target]=low[target]=++tot;
    for(int i=head[target];i;i=next[i])
    {
        if(!use[to[i]])
        {
            tarjan(to[i]);
            low[target]=std::min(low[target],low[to[i]]);
        }
        else if(ins[to[i]]) low[target]=std::min(low[target],deep[to[i]]);
    }
    if(low[target]==deep[target])
    {
        ans++;
        int tmp;
        do
        {
            tmp=st[top--];
            ins[tmp]=false;
            f[ans][++f[ans][0]]=tmp;
        }while(tmp!=target);
        if(f[ans][0]==1) --f[ans--][0];
    }
    return;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&inx,&iny);
        to[++cnt]=iny;
        next[cnt]=head[inx];
        head[inx]=cnt;
    }
    for(int i=1;i<=n;++i)
    {
        if(!use[i]) tarjan(i);
    }
    printf("%d\n",ans);
    /*for(int i=1;i<=ans;++i)
    {
        for(int j=1;j<=f[i][0];++j) printf("%d ",f[i][j]);
        printf("\n");
    }*/
    cnt=0;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=ans;++i)
        for(int j=1;j<=f[i][0];++j)
        {
            ++cnt;
            fa[f[i][j]]=f[i][1];
        }
    for(int i=1;i<=n;++i)
        for(int j=head[i];j;j=next[j])
        {
            if(fa[to[j]]==fa[i]) continue;
            res[fa[i]]++;
        }
    for(int i=1;i<=ans;++i)
    {
        if(res[f[i][1]]==0)
        {
            if(flg)
            {
                flg=false;
                break;
            }
            flg=true;
            temp=i;
        }
    }
    if(flg)
    {
        std::sort(f[temp]+1,f[temp]+f[temp][0]+1);
        for(int j=1;j<=f[temp][0];++j) printf("%d ",f[temp][j]);
    }
    if(!flg) printf("-1");
    return 0;
}

JDOJ1833 校园网

题目大意:请你求出一个有向图遍历全图至少需要选择几个点作为起点,以及如果想整体成为一个强连通分量所需要添加几条边。

这道题首先通过Tarjan将整个图缩为一个DAG,之后遍历找到入度为0和出度为0的新图上点的个数,入度为0的个数为第一问解,二者最大值为第二问解。

证明如下:入度=0的点不被任何点连接,为了是所有点被联通,自然要对其进行优先染色。为了保证最后生成的是图整体强连通,那么就需要保证有一条有向边从入度为0的点出发到强连通分量里面去,或者有一条有向边从强连通分量出发到出度=0的点去

附AC代码。

#include <cstdio>
#include <algorithm>
 
int n,to[10000],head[10000],next[10000],st[110],deep[110],low[110],ans,tot,cnt,top,icnt[210],ocnt[210],ansa,ansb,belong[110];
bool ins[110],use[110];
 
void tarjan(int target)
{
    st[++top]=target;
    ins[target]=true;
    use[target]=true;
    deep[target]=low[target]=++tot;
    for(int i=head[target];i;i=next[i])
    {
        if(!use[to[i]])
        {
            tarjan(to[i]);
            low[target]=std::min(low[target],low[to[i]]);
        }
        else if(ins[to[i]])
            low[target]=std::min(low[target],deep[to[i]]);
    }
    if(deep[target]==low[target])
    {
        ans++;
        int tmp;
        do
        {
            tmp=st[top--];
            ins[tmp]=false;
            belong[tmp]=ans;
        }while(tmp!=target);
    }
    return;
}
 
 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        while(1)
        {
            scanf("%d",&to[++cnt]);
            if(!to[cnt])
            {
                --cnt;
                break;
            }
            next[cnt]=head[i];
            head[i]=cnt;
        }
    for(int i=1;i<=n;++i)
        if(!use[i]) tarjan(i);
    for(int i=1;i<=n;++i)
        for(int j=head[i];j;j=next[j])
            if(belong[to[j]]!=belong[i])
            {
                ++icnt[belong[to[j]]];
                ++ocnt[belong[i]];
            }
    for(int i=1;i<=ans;++i)
    {
        if(!icnt[i]) ++ansa;
        if(!ocnt[i]) ++ansb;
    }
    if(ans==1)
    {
        printf("1\n0");
        return 0;
    }
    printf("%d\n%d",ansa,std::max(ansa,ansb));
}

JDOJ1432 桐桐的糖果计划

题目大意;给你一个无向图,求这个无向图的割边数量以及至少需要加多少条边才能使整个图变成一个完全的双联通图。

这道题我们可以用另一种方法进行Tarjan:针对无向图的Tarjan.有向图的tarjan求的是强连通分量,即每一个点都能直接或间接抵达另外的所有点,而无向图的Tarjan则是针对无向图进行搜索,找到一个子图,是的任意两点间都有两条或两条以上的完全不相同的路径。

我们通过这种Tarjan得到的是一个无向图的双联通分量,即一个子图中每两个点之间至少有2条可行路径。

在进行Tarjan求无向图割边的时候,我们在每一次Tarjan函数内递归后加上一句判断语句:如果向下递归的那个节点不使用这条边返回该节点则达不到任何比这个点还要靠前的点,那么这个节点下方的联通块就被“憋住”了,这条边则为割边。

第二问,有向图Tarjan之后得到的是一个DAG(有向无环图),因为如果有一个环那么这个环也应加入强连通分量中。而无向图的Tarjan最终得到的是一棵树——满足任意两点之间都无法构成一个环,而连接任意两个点那么就会构成一个环,于是,我们可以得到,如果这棵树有t个叶子结点,那么连接他们得到一个完全的两两可达的双连通分量就需要连接ceil((t+1)/2)条边。

 

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - Tarjan求强连通分量


不骗了,不骗了。
A Simple OIer fighting tooth and nail.