Tarjan学习笔记

有向图强连通分量

定义

在有向图中，如果存在极大子图中从任意一点出发均能到达其他所有点，则称这个子图为有向图的强连通分量。

Tarjan求强连通分量

如果将这个有向图dfs成一棵树，当其加入一条边使得有向树中形成环时，这个环上的所有点都属于同一个强连通分量。当且仅当，加入的边从当前节点指向该节点的祖宗节点时，才有可能出现环；而且当存在当前节点指向该节点的祖宗节点时，若有加入一条起点终点深度相同的边，并且从终点可以走到连向祖宗节点的边的点，该祖宗节点也能走到加入的边的起点，图中也能形成新的环。

dfn[i] 用来记录第 i 个点的dfs序， low[i] 表示第 i 个点加边之后可以走到最靠上的点的dfs序。

dfs的起点为图中所有入度为零的点，枚举以当前节点 now 为起点的所有边的终点，如果该终点还没有被dfs过，则先dfs这个点，再用该终点的 low 值更新 low[now] 的值 ，如果该终点已经被dfs过了，该终点有可能是祖宗节点，则用该终点的dfs序更新 low[now] 的值。

如果某个点所连向的其他点没有dfs完成，或者该节点不知道处于哪个确定的强连通分量中，则不将该节点弹栈。

如果某个点的 dfn 值与 low 值相同，则说明该节点处存在一个强连通分量，而且该强连通分量的其他点均没有被弹栈，并在栈中被排在当前节点的后面，所以对这些点进行出栈以及加到同一个强连通分量中。

代码

  • 通过DFS求强连通分量
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
void dfs(int now) {
    int size = 0;
    t++;
    dfn[now] = low[now] = t;
    instack[now] = true;
    s[++size] = now;
    for(int i = first[now]; i; i = ed[i].next) {
        int e = ed[i].e;
        if(!dfn[e]) {
            dfs(e);
            low[now] = min(low[now], low[e]);
        }
        else {
            if(instack[e]) low[now] = min(low[now], dfn[e]);
        }
    }
    if(dfn[now] == low[now]) {
        cnt++;
        belong[now] = cnt;
        while(s[size] != now) {
            belong[s[size]] = cnt;
            instack[s[size]] = false;
            size--;
        }
        size--;
        instack[now] = false;
    }
}
  • 缩点
1
2
3
4
5
6
7
8
9
10
11
12
void suodian() {
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) dfs(i);

    for(int i = 1; i <= n; i++)
        for(int j = first[i]; j; j = ed[j].next)
            if(belong[i] != belong[ed[j].e])
                add_edge2(belong[i], belong[ed[j].e], ed[j].d);
    
    for(int i = 1; i <= n; i++)
        value[belong[i]] += v[i];
}
  • 拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void toposort() {
    int size = 0;
    for(int i = 1; i <= cnt; i++)
        if(!in[i]) q[++size] = i;
    for(int i = 1; i <= n; i++) {
        int now = q[i];
        for(int j = first[now]; j; j = ed[j].next) {
            int e = ed[j].e;
            in[e]--;
            if(!in[e]) q[++size] = e;
        }
    }
}

无向图双连通分量

定义

  • 割点：删掉这个点则图不连通，则称这个点为割点

  • 桥：删掉这条边则图不连通，则称这个边为桥

  • 边双连通分量：找到一个尽量大的子图，使得这个子图里没有桥，其中每个点只可能在一个边双连通分量中

  • 点双连通分量：找到一个尽量大的子图，使得这个子图里没有割点（指子图内没有割点，而不是子图中不包含全局割点），其中每个点可能在多个点双连通分量中（不要求掌握）

Tarjan求无向图边双连通分量

每条无向边只允许走一次，对无向图进行一次与有向图相似的dfs。

代码

  • 通过dfs求边双连通分量

其中 from 为来这个点的边，由于第七行判定是否枚举到的边的方式为判断这两边的编号是否相邻，并且偶数边会判断边号加一的奇数边，同时奇数边会判断编号减一的偶数边，所以建图时推荐从边号2开始。

如果一个连接 ii 、 jj 两个结点的边是桥，假设后dfs到的点是 jj 号点，则 dfn[i] 一定小于 low[j] ，因为 jj 点能找到的点一定比 ii 点后dfs。

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
void dfs(int now, int from) {
    t++;
    dfn[now] = low[now] = t;
    vis[now] = true;
    for(int i = first[now]; i; i = ed[i].next) {
        int e = ed[i].e;
        if((i ^ 1) != from) {
            if(!dfn[e]) {
                dfs(e, i);
                low[now] = min(low[now], low[e]);
            }
            else {
                if(vis[e]) low[now] = min(low[min], dfn[e]);
            }
        }
        vis[e] = false;
    }
}
void find_bridge {
    for(int i = 1; i <= n; i++)
        for(int j = first[i]; i; i = ed[i].next) {
            int e = ed[j].e;
            if(low[e] > dfn[i] || low[i] > dfn[e]) ed[i].bridge = true;
        }
}
void find_bcc(int now) {
    vis[now] = true;
    for(int i = first[now]; i; i = ed[i].next) {
        int e = ed[i].e;
        if(!ed[i].bridge && !vis[e]) {
            belong[e] = cnt;
            find_bcc(e);
        }
    }
}
void suodian() {
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) dfs[i];
    find_bridge();
    memset(vis, false, sizeof(vis));
    for(int i = 1; i <= n; i++)
        if(!vis[i]) find_bcc(i);
    
    for(int i = 1; i <= n; i++)
        for(int j = first[i]; j; j = ed[j].next)
            if(belong[i] != belong[ed[j].e]) add_edge2(belong[i], belong[ed[j].e], ed[j].d);
    
    for(int i = 1; i <= n; i++)
        value[belong[i]] += v[i];
}