【蒟蒻图论】tarjan及其经典运用(一)

终于到图论部分了,图论我是真心弱啊QwQ。今天复习了一下tarjan,总结了一下其基本用法,希望对你有帮助吧。

什么是tarjan?

tarjan算法又称“塔尖”算法,是解决图联通问题的一种神奇算法。换句话说,tarjan就是基于DFS算法,对每个点进行标记处理的一种基本图论算法。

tarjan有什么用?

由于tarjan是解决图联通的一种算法(:з」∠),所以我们很自然的可以想到可以用来求强联通分量,割点,割边以及很经典的tarjan缩点。下面我们就一个一个来介绍这些经典的运用。这篇博客我们就先来求解强连通分量。

求强连通分量

强连通和强连通图

在一个有向图G里,设两个点x.y。若由x有一条路可以走到y,由y又有一条路可以走到x,我们就叫这两个顶点(x,y)强连通。

同理,如果 在一个有向图G中,任意两个点都强连通,我们就叫这个图,强连通图,特殊的,每一个单独的点都是一个强连通子图。

强联通分量

2.jpg

算法详解

首先我们要知道几个数组的含义:

struct node
{
    int x,y,next;
}a[110000];
int last[110000];
//数组a,last用前向星存储这幅图
int dfn[110000],low[110000],visit[110000],stack[110000],heads[110000];
//dfn【i】代表第i个点的搜索次序,也就是时间戳,换句话说,就是记录这个点是第几个被找到的,所以显然每个点的dfn都不一样。
//low【i】代表从这个点,可以到达时间戳最小的点。由于是这一幅图而不是一棵树,所以某个点的叶子节点可以是他的祖先,详细见下面的伪代码。
//visit数组和表面意思一样,就是记录某个点是否被访问过,若第i个点被访问,则visit【i】=1,反正为0.
//*stack数组顾名思义,是一个操作中栈,存储的是还没有确定归属于哪个强连通的点,是非常重要的数组,下文会详细讲解。
//head记录的是每个强连通分量的头结点(就是时间戳最小的那一个)。

我们来看看伪代码:

tarjan(u){

  dfn[u]=low[u]=++Index 
  // 为节点u设定次序dfn【u】编号和low【u】初值,其中刚开始时,low【u】的值就为dfn【u】的值

  Stack.push(u)   // 将节点u压入栈中

  for each (u, v) in E // 枚举每一条边

    if (v is not visted) // 如果节点v未被访问过

        tarjan(v) // 继续向下找

        Low[u] = min(Low[u], Low[v])

    else if (v in S) // 如果节点u还在栈内

        Low[u] = min(Low[u], LOW[v])
        //就是如果他的儿子节点是他的祖先,那么他最先能到达的点就是他这个祖先最先能到达的点。

  if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根
    head[++]=u;// u号点为该强连通分量的头节点
  repeat v = S.pop  // 将v退栈,为该强连通分量中一个顶点

  print v

  until (u== v)//当退栈推完u点,也就是这个强连通分量的头顶点时,就可以停止了。

}

没看懂?没关系,下面我们就用一个很热门的图来讲解一下:3.PNG
首先1号点入栈,时间戳为1;dfn[1]=low[1]=1;
4.png
接着从1号点开始深搜,首先发现3号点,3号点入栈,时间戳为2,dfn[3]=low[3]=2;
5.png
接着从3号点开始深搜,首先发现5号点,5号点入栈,时间戳为3,dfn[5]=low[5]=3;
6.png;
同理接着从5号点开始深搜,发现6号点,6号点入栈,时间戳为4,dfn[6]=low[6]=4;
7.png
我们发现6号没有子节点,无法拓展,又发现dfn[6]==low[6],所以我们已经找到了以6为头元素的第一个强连通分量。我们把栈中6及6后面所有的元素退栈(只有6),head中加一个6,它们(只有6)构成一个强连通分量。
8.png
接着我们退回到5号节点,发现5号也没有其他子节点了,且dfn[5]==low[5],所以我们已经找到了以5为头元素的又一个强连通分量。我们把栈中5和5后面所有的元素退栈(只有5),head中加一个5;
9.png
接着我们退回到3号节点,发现还有一个子节点4,4入栈,时间戳为5,dfn[4]=low[4]=5;
10.png
然后我们从4号点开始深搜,发现6号点,6号已经被访问过了且不在stack数组里,所以不用理他。接着我们发现4的另一个子节点1,1号点被访问过,且在stack里所以我们用low[1]来替换low[4];
11.png
接着我们发现4号点已经没有子节点了,但是dfn[4]!=low[4],所以4号点不是某个强连通分量的头节点,我们直接退回3号点。我们发现low[4]小于low[3]所以用low[4]来替换low[3];
12.png
然后我们退回到1号点,发现1号点还有一个没有被发现过的儿子2,于是2入栈,时间戳为6,dfn[2]=low[2]=6;
13.png
然后我们发现2只有一个儿子4,且4号点被访问过且在stack里,并且low[4]小于low[2],所以用low[4]来替换low[2];
14.png
2号点没有其他儿子可以访问了,dfn[2]!=low[2],所以2号点不是某个强连通分量的头节点,我们直接退回1号点。
接着我们发现1号点也没有其他儿子可以访问了,且dfn[1]==low[1],所以1是一个强连通分量的头元素,于是head中加一个1,把stack中1和1之后的元素退栈(有1,3,4,2),这四个点构成强连通分量。
13.png
然后我们发现全部点都被访问过了,tarjan就结束了。
【PS 若是还有点没被访问过怎么办?那就从那个点开始再跑一次tarjan,直到所以点都被遍历过】

代码实现

模板就很简单了QwQ

int tarjan(int x)
{
    tot++;dfn[x]=tot;low[x]=tot;
    stack[++indexx]=x;
    visit[x]=1;

    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=my_min(low[x],low[y]);
        }
        else
if(visit[y]==1)low[x]=my_min(low[x],low[y]);

    }

    if(dfn[x]==low[x])
    {
        head[hk++]=u;
        do
        {
            fprintf(fout,"%d ",stack[indexx]);  
            visit[stack[indexx]]=0;  
            indexx--;  
        }
        while(x!=stack[indexx+1]);

        fprintf(fout,"\n"); 

    }
    return 0;

}

模板题

【caioj 1147】强连通

【题目描述】
给出一个有向图有n个点和m条有向边,输出连通分量的数量。
概念:

  1. 什么是连通分量?
    答:一个有向图中,选出某些点组成一个团体,这个团体中的任意两点都可互相到达。那么:选出来的这些点+这些点之间原有的边=叫做 连通分量。
  2. 只适合有向图
    答:如果是无向图,那么并查集就可以解决了(还记得“家族”吗?)
    附加1:什么是强连通图?
    答:如果有向图G的任意两个顶点都可以互相到达,称G是一个强连通图。
    附加2:什么是强连通分量?
    答:比如GG是G的最大的强连通子图,称为G的强连通分量(可能不止一个,这个不重要)
    cai.png
    比如输入样例1,有3个连通分量:(1)、(2,3,4,5,6)、(7)
    比如输入样例2,有3个连通分量:(1,2,3)、(4,6,7)、(5)
    【输入格式】
    第一行n和m(1<=n<=20000,1<=m<=20 0000),表示有向图总共n个点,点的编号由1~n。m表示m条有向边。
    下来m行,每行两个整数x和y,表示一条有向边从点x出发到点y。
    【输出格式】
    一行一个整数,表示连通分量的个数。
    【样例1输入】
    7 7
    1 2
    2 3
    3 4
    4 5
    5 6
    6 2
    5 2
    【样例1输出】
    3
    【样例2输入】
    7 11
    1 2
    1 4
    2 3
    2 5
    3 1
    3 5
    3 6
    4 6
    5 7
    6 7
    7 4
    【样例2输出】
    3

很明显就是要求强连通分量的数量,直接套模板就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
struct node
{
    int x,y,next;
}a[210000];
int last[210000];

int dfn[210000],low[210000],visit[210000],stack[210000],heads[210000];
int i,j,k,m,n,o,p,js,jl,tot,indexx,len,u,v;
using namespace std;

int my_min(int x,int y)
{
    if(x<y)return(x);
    else return(y);
}
int ins(int x,int y)
{
    len++;
    a[len].x=x;a[len].y=y;
    a[len].next=last[x];
    last[x]=len;
}

int tarjan(int x)
{
    tot++;dfn[x]=tot;low[x]=tot;
    stack[++indexx]=x;
    visit[x]=1;

    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=my_min(low[x],low[y]);
        }
        else if(visit[y]==1)low[x]=my_min(low[x],low[y]);

    }

    if(dfn[x]==low[x])
    {
        js++;
        do
        {  
            visit[stack[indexx]]=0;  
            indexx--;  
        }
        while(x!=stack[indexx+1]);

    }
    return 0;

}

int main()
{
    scanf("%d%d",&n,&m);
    memset(dfn,0,sizeof(dfn));
    len=0;tot=0;indexx=0;js=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ins(u,v);
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0)
        tarjan(i);
    }
    printf("%d\n",js);
    return 0;
}

结语

是不是很浅显易懂呢?下篇博客我们将从tarjan其他的应用入手,带你走进你也许早已学会的tarjan算法。

Last modification:July 12th, 2018 at 05:30 pm
If you think my article is useful to you, please feel free to appreciate

8 comments

  1. ass

  2. gay

    逼牛伟本卢

  3. cckk

    楼上说的太对了

    1. jvruo
      @cckk

      您太强了Orz

  4. 寒夏Sama

    太巨了Orz

    1. jvruo
      @寒夏Sama

      我何能及君也⌇●﹏●⌇

  5. 孤独的木薯

    贪玩蒟蒻,真尼玛好玩!(/ω\)

    1. jvruo
      @孤独的木薯

      那是相当好玩(/ω\)

Leave a Comment