Zth's Blog

记录学习路上的点滴

0%

Tarjan算法与图的连通性

发表于 分类于

参考lyd《算法竞赛进阶指南》

Tarjan算法与无向图连通性

一些概念

割点和桥

给出无向连通图$G = (V, E)$

​ 若对于$x \in V$， 从图中删去$x$以及所有与$x$相关的边之后， $G$分解为两个或两个以上不相连的子图， 则称$x$为$G$的一个割点

​ 若对于$e \in E$， 从图中删去边$e$之后， $G$分裂为两个不相连的子图， 则称$e$为$G$的一条割边或桥

时间戳

在图的深度优先遍历中， 按照每个节点第一次被访问的时间顺序， 一次给予$N$个节点$1 … N$的整数标记， 该标记就被叫做时间戳， 用$dfn[x]$来表示

搜索树

在无向连通图中任选一个节点出发进行深度优先遍历， 每个节点只访问一次。 所有发生递归的边$(x, y)$(即从$x$到$y$是对$y$的第一次访问)构成一棵树， 我们把它称为无向连通图的搜索树。 如果图本身不连通， 则会出现一个搜索森林

追溯值

$Tarjan$算法引入一个追溯值$low[x]$。 设$subtree(x)$表示搜索树中以$x$为根的子树。 $low[x]$定义为以下节点的时间戳的最小值

  1. $subtree(x)$中的节点
  2. 通过$1$条不在搜索树中的边， 能够到达$subtree(x)$的节点

根据定义， 为了计算$low[x]$， 先令$low[x] = dfn[x]$， 然后考虑从$x$出发的每条边$(x, y)$

  1. 在搜索树上$x$是$y$的父节点， 则令$low[x] = min(low[x], low[y])$
  2. $(x, y)$不是搜索树上的边， 则令$low[x] = min(low[x], dfn[y])$

割边判定法则

无向边$(x, y)$是桥， 当且仅当搜索树上存在$x$的一个子节点$y$， 满足$dfn[n] < low[y]$， 即从$y$出发， 不能回到$x$或者早于$x$的节点， 那么删去这条边， $x$与$y$将不再连通

显然， 桥一定是搜索树上的边， 并且简单环上的边都不是桥

代码

与求解割点的代码类似， 所以这里不特别给出， 只需注意$tarjan函数$中传参额外传一个入边的编号而不是父节点编号以应对重边的情况， 建边时边的编号使用成对存储

割点判定法则

若$x$不是搜索树的根节点， 则$x$是割点当且仅当搜索树上存在$x$的一个子节点$y$满足$dfn[x] \leq low[y]$， 即$y$不能追溯到早于$x$的节点， 删去$x$， $y$将与其所有祖先节点不可达

若$x$是搜索树的根节点， 则$x$是割点当且仅当$x$有两个或两个以上的子节点

代码

题目为洛谷模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstdio>

int n, m;
int tot, head[20004];
struct Edge
{
    int from, to, next;
} edge[200005];
int num, dfn[20004], low[20004];
int root;
bool cut[20004];
int cnt;

void Addedge(int u, int v)
{
    edge[++ tot] = (Edge){u, v, head[u]};
    
    head[u] = tot;
}

void Tarjan(int u)
{
    low[u] = dfn[u] = ++ num;
    
    int child = 0;
    bool is_root = (u == root);
    
    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;
        
        if(! dfn[v])
        {
            child ++;
            
            Tarjan(v);
            
            low[u] = std:: min(low[u], low[v]);
            
            if(is_root == false && low[v] >= dfn[u])
            {
                if(! cut[u]) cnt ++;
                
                cut[u] = true;
            }
        }
        else
            low[u] = std:: min(low[u], dfn[v]);
    }
    
    if(is_root && child > 1)
    {
        if(! cut[root]) cnt ++;
        
        cut[root] = true;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++)
    {
        int u, v;
        
        scanf("%d%d", &u, &v);
        
        Addedge(u, v);
        Addedge(v, u);
    }
    
    for(int i = 1; i <= n; i ++)
        if(! dfn[i])
            root = i, Tarjan(i);
    
    printf("%d\n", cnt);
    for(int i = 1; i <= n; i ++)
        if(cut[i]) printf("%d ", i);
    
    return 0;
}

Tarjan算法与有向图连通性

一些概念

流图

给定有向图$G = (V, E)$， 若存在$r \in V$， 满足从$r$出发能到达$V$中所有的点， 则称$G$是一个流图(Flow Graph)， 记为$(G, r)$， 其中$r$称为流图的源点

搜索树

在一个流图$(G, r)$上从$r$出发进行深度优先遍历， 每个点只访问一次。 所有发生递归的边$(x, y)$， 构成一棵以$r$为根的树， 我们把它称为流图$(G, r)$的搜索树

时间戳

在深度优先遍历中， 按照每一个节点第一次被访问的时间顺序， 依次给予流图中的$N$个节点$1 … N$的整数标记， 该标记称为时间戳， 记为$dfn[x]$

流图中的每条有向边$(x, y)$可以分为四类

  1. 树枝边， 指搜索树中的边， 即$x$是$y$的父节点
  2. 前向边， 指搜索树中$x$是$y$的祖先节点
  3. 后向边， 指搜索树中$y$是$x$的祖先节点
  4. 横叉边， 指除了以上三种情况之外的边， 它一定满足$dfn[y] < dfn[x]$

有向图的强连通分量

给定一张有向图， 若对于图中的任意两个节点$x, y$， 既存在从$x$到$y$的路径， 也存在$y$到$x$的路径， 则成该有向图是强连通图

有向图的极大强连通子图被称为强连通分量， 简称为SCC

追溯值

设$subtree(x)$表示流图的搜索树中以$x$为根的子树。 $x$的追溯值定义为满足以下条件的节点的最小时间戳

  1. 该点在栈中
  2. 该点不在栈中， 存在一条从$subtree(x)$出发的有向边， 以该点为终点

根据定义， 我们按照如下方法计算追溯值

  1. 当节点$x$第一次被访问时， 把$x$入栈， 初始化$low[x] = dfn[x]$

  2. 扫描从$x$出发的每条边$(x, y)$

    (1)若$y$没有被访问过， 则说明$(x, y)$是树枝边， 递归访问$y$， 从$y$回溯之后， 令$low[x] = min(low[x], low[y])$

    (2)若$y$被访问过并且$y$在栈中， 则令$low[x] = min(low[x], dfn[y])$

    ​ PS: 存在$y$被访问过但是$y$不在栈中的情况， 此时$(x, y)$为横叉边

强连通分量判定法则

在追溯值计算的过程中， 若从$x$回溯前， 有$low[x] = dfn[x]$成立， 则栈中从栈顶到$x$的所有节点构成一个强连通分量

因为$x$不能追溯到其前面的点， 也已经从$x$搜索找到了所有可达的点， 而栈中所有的点都可追溯到$x$(如果栈中有点不能追溯到$x$， 那它应该在回溯到$x$前已经被弹出栈了)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void Tarjan(int u)
{
    dfn[u] = low[u] = ++ p;
    S.push(u);
    vis[u] = true; // vis表示是否在栈

    for(int i = head[u]; i; i = edge[i].next)
    {
        int v = edge[i].to;

        if(! dfn[v])
            Tarjan(v), low[u] = std:: min(low[u], low[v]);
        else if(vis[v])
            low[u] = std:: min(low[u], dfn[v]);
    }

    if(dfn[u] == low[u])
    {
        while(S.top() != u)
        {
            int now = S.top();
            
            S.pop();
            vis[now] = false;
        }

        S.pop();
        vis[u] = false;
    }
}

需要注意的是第$14$行代码， 如果写成low[u] = std:: min(low[u], low[u])也是对的， 不过如果严格根据定义， 不应该这样写

如果在割点和桥的时候这样写， 会出错， 因为不满足了追溯值的定义

如上图所示， 节点编号即为其$dfn$， 绿色的边为搜索树上的边

如果我们的写法是low[u] = std:: min(low[v], low[u])， 在进行完红圈的搜索后， 由于$low[5] = 2$， 回溯到$3$时会有$low[4] = 2, low[3] = 2$， 然后进行蓝圈的搜索会有$low[7] = low[6] = 2$， 这个时候$3$号点就不会被判断为割点， 因为$6, 7$通过它的另一个环找到了比它更早的点， 这显然是错误的， 和我们定义的通过$1$条不在搜索树上的边冲突， 所以出错也是理所应当