Tarjan

Robert Tarjan,是美国的计算机科学家,在1986年获得图灵奖。在LCA的blog中也有提到求解LCA的Tarjan算法。这一篇的Tarjan算法是求解强连通分量、割点和桥的。

强连通分量

有向图强连通分量:在有向图G中,如果两个顶点vi,vj间(vi>vj)有一条从vi到vj的有向路径,同时还有一条从vj到vi的有向路径,则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量(strongly connected components)。

求解强连通分量、割点、桥的Tarjan算法都差不多,都是通过DFS来找的。

在Tarjan算法中,有两个非常重要的变量。

dfn[i] : 表示第i个顶点在dfs中第几个访问(时间戳)

low[i] : 表示第i个顶点可以回溯到的最早访问的顶点

可能这样说难以理解,一会看图解和代码就理解了。

在求解强连通分量时,为了知道一个强连通分量有哪些顶点,还需要用到stack。

Tarjan求解强连通分量的伪代码如下

low[u] = dfn[u] = ++ind;
ins[u] = 1;
stack.push(i);
for v in <u, v>:
    if(v is not visited):
        Tarjan(v)
        low[u] = min(low[u], low[v]);
    else if(v in stack):
        low[u] = min(low[u], dfn[v]);

if(low[u] == dfn[u]):
    int p;
    cnt++;
    do:
        p = stack.top;
        stack.pop;
        ins[p] = 0;
        belong[p] = cnt;
    while(p != u)

图解来辽,就用下面这个图来做例子吧

0

然后根据DFS,到下图

1

这时候访问到顶点5,已经没法继续DFS了,并且low[5] = dfn[5],说明存在强连通分量。把栈中的元素依次出栈,直到遇到了顶点5。这里只出栈了顶点5,说明顶点5单独成为一个强连通分量。

回退到顶点3

2

这时候和刚刚的情况一样,顶点3单独成为一个强连通分量。

3

回退到顶点2,DFS遍历顶点4.

4

这时候顶点4发现顶点1已经遍历过了,所以更新顶点4的low为1.

5

回退到顶点2,更新顶点2的low

6

回退到顶点1,发现low[1] = dfn[1],将栈中的元素出栈,知道遇到1。这时候顶点1、 2、 4成为一个强连通分量。

7

到这里整个算法就结束了~

模板如下:

vector<int> g[maxn];
int low[maxn], dfn[maxn], sta[maxn], ins[maxn], belong[maxn];
int cnt, ind, tot; //cnt:强连通分量的数量, ind:时间戳, tot:sta的top

void init()
{
    memset(ins, 0, sizeof(ins));
    memset(belong, 0, sizeof(belong));
    memset(dfn, 0, sizeof(dfn));
    cnt = ind = tot = 0;
}

void Tarjan(int u)
{
    low[u] = dfn[u] = ++ind;
    ins[u] = 1;
    sta[++tot] = u;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(ins[v])
            low[u] = min(low[u], dfn[v]);
    }
    int p;
    if(low[u] == dfn[u])
    {
        ++cnt;
        do
        {
            p = sta[tot--];
            belong[p] = cnt;
            ins[p] = 0;
        }while(p != u);
    }
}

割点

在一个无向图中,如果删除一个顶点及与它相关联的边之后,图的连通分量增多了,则称这一个点为割点。

对于根节点来说,只要它至少有两颗子树,那么根节点一定是割点。对于其它顶点来说则麻烦一些。

回想一下Tarjan算法中low的意义,表示该顶点能够回溯到最早访问的顶点的序号。对于一个顶点来说,在它之前访问的一个顶点是该顶点的父亲,在它父亲之前的是它的祖先,若该顶点能够不通过父亲就回溯到祖先的话,那么说明该顶点的父亲不是割点。所以,若一个顶点的所有儿子都能够不通过它自己就能回溯到祖先顶点,则该顶点不是割点,否则就是割点。

所以对于边<u, v>来说,若low[v] >= dfn[u],则u是割点。

8

对于上图来说,顶点2和3都是割点。

模板如下

vector<int> g[maxn];
// iscut[i]: 若顶点i是割点,则为1,反之为0
int low[maxn], dfn[maxn], iscut[maxn];
int ind;

void init()
{
    memset(dfn, 0, sizeof(dfn));
    memset(iscut, 0, sizeof(iscut));
    ind = 0;
}

// pa为u的父节点,初始时Tarjan(i, i)
void Tarjan(int u, int pa)
{
    int cnt = 0; //用来记录子树的数量
    low[u] = dfn[u] = ++ind;
    for(int i=0;i<g[u].size();i++)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            // 若low[v]>=dfn[u],并且u不是根节点,则u是割点
            if(low[v] >= dfn[u] && pa!=u)
                iscut[u] = 1;
            // 若u是根节点,则cnt++
            if(u == pa)
                cnt++;
        }
        else if(v != pa) //若v不等于父节点
            low[u] = min(low[u], dfn[v]);
    }
    if(cnt>=2 && u==pa) //根节点子树数量大于等于2,则为割点
        iscut[u] = 1;
}

桥也叫割边,对于边e来说,若去掉了e,图的连通分量增多了,则说明e为桥。

找割边和找割点很像。对于边<u, v>来说,若low[v] > dfn[u], 则<u, v>是桥。

8

所以对于上图来说,边<2, 3>和<3, 5>都是桥。

模板:

// 用链式前向星来存储边
struct Edge
{
    // iscut表示是否为桥
    int to, next, iscut;
}e[maxn*maxn*2];

int head[maxn], low[maxn], dfn[maxn];
int ind, tot; // tot是边的数量

void init()
{
    memset(head, -1, sizeof(head));
    memset(dfn, 0, sizeof(dfn));
    ind = tot = 0;
}

void addedge(int u, int v)
{
    e[tot].to = v;
    e[tot].next = head[u];
    e[tot].iscut = 0;
    head[u] = tot++;
}

void Tarjan(int u, int pa)
{
    low[u] = dfn[u] = ++ind;
    for(int i=head[u]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == pa) continue;
        if(!dfn[v])
        {
            Tarjan(v, u);
            low[u] = min(low[u], low[v]);
            // 是桥
            if(low[v] > dfn[u])
            {
                // 因为加边时,是加双向边的,所以编号0和1, 2和3...等是一对边,i^1就能取到另一条边,可自行测试
                e[i].iscut = e[i^1].iscut = 1;
            }
        }
        else
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

END

Tarjan还可以用来缩点,emmm咕咕咕。
溜~