Tarjan 相关算法学习笔记

Posted on 2023-01-23 In XCPC , Note

简要汇总了 Tarjan 相关的图论算法的资料, 并有所思考.

Tarjan 的思路是很有代表性的.

运用 Tarjan 的图论算法主要有:

求有向图的强连通分量(缩点为 DAG)
求无向图的割点、桥.
求无向图的双连通分量(点、边)

Tarjan 思路总结

Tarjan 的思路是先找出图的一棵生成树, 则沿着树任意两点构成唯一的一条路径. 剩下的边分为横叉边和返祖边, 这样的边构成环(从而构成强连通/双连通). Tarjan 富有特色地使用了 \(low\) 数组统计了连通性相关的信息. 由于我们要求的是连通分量, 所以信息不会丢失.

求强连通分量(SCC)

题目链接: LG_P3387 缩点

理论

可以想象, 在一棵完整的生成树中, SCC 是分层的(也就是说, SCC 沿着生成树的边也是一种树形结构), 所以我们使用栈记录 SCC 上的节点. 具体地说, 在生成树上, 一个 SCC 是一种类似于"树段"的结构. 它以一个点 \(u\) 作为"根", 有 \(u\) 的子树中的若干节点 \(x_1, x_2, \cdots, x_m\) 作为"叶子", 而所有 SCC 中的节点就是生成树上 \(u\to x_i\) 路径上的点的并. 我们记这样的 SCC 为 \(SCC(u)\). \(x_i\) 一定至少满足以下两性质之一:

\(x_i\) 存在返祖边 \((x_i, u)\).
\(x_i\) 存在横叉边 \((x_i, t)\), 其中 \(t\) 比 \(x_i\) 时间戳小且在 \(SCC(u)\) 中.

注意, 以上定义中横叉边一词必须依托时间戳而存在.

那么, 我们的 \(low\) 数组就细致地描述了这个过程. 如果我们在每个 SCC 的根 \(u\) 处考虑哪些节点在 \(SCC(u)\) 中, 那么我们只需要排除所有 \(x_i\) 的孩子们, 它们开启了新的 SCC. 还记得我们上面说使用栈维护 SCC 吗? 我们在 dfs 树找到一个新的 SCC 后, 从栈中弹出它们即可更新答案的同时给它的父亲 SCC "排异".

如果对于一个节点 \(v\) 有返祖边 \((v, u)\), 则这说明 \(v\) 所在的 SCC 的根至少是 \(u\), 或者 \(u\) 的祖先. 那么我们可以往上传递(根据 SCC 的树段结构), 对 \(u\to v\) 的每个节点, 至少可以到 \(u\), 故其所在的 SCC 的根至少是 \(u\), 或者 \(u\) 的祖先.
如果对于一个节点 \(v\) 有横叉边 \((v, x)\). 分为两种情况:
- 若 \(x\) 已经出栈, 那么 \(x\) 所在的 SCC 已经被考虑. 那么沿着 \((v, x)\) 继续走只能在 \(x\) 所在的 SCC 及其子 SCC 里面绕, 绝不可能到达 \(u\) 的祖先(否则, 这个 SCC 应该再扩大, 需要到 \(u\) 的祖先处再确定), 故它没有作用.
- 若 \(x\) 仍然在栈中, 则 \(x\) 所在的 SCC 仍未完全确定, 它的根是 \(u\) 的祖先, 那么继续沿着 \(u\) 走可以回到它的祖先, 那么它的作用就类似于一条返祖边了. 可以类似与返祖边的做法.

于是我们的 \(low\) 定义就是基于上面的分析来的. 在遍历完 \(u\) 的所有子树时, \(low(u)\) 集齐了 \(u\) 子树的可达性分析, 得到了从 \(u\) 出发的可以到达的最浅祖先. (事实上不完全是这样, 见下方写法对比) 则当 \(low(u)=dfn(u)\) 时, 代表一个 SCC 的根, 这时仍在栈中且在 \(u\) 子树中的节点(或者说栈中在 \(u\) 以上的节点, 含)就是以 \(u\) 为根的 SCC 的节点.

写法对比

void tarjan(int u) {
    dfn[u] = low[u] = ++_dfn;
    stk[++top] = u;
    ins[u] = 1;
    for(int i = G1.head[u]; i; i = G1.e[i].nxt) {
        int v = G1.e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(ins[v]) {
            low[u] = min(low[u], low[v]); //写法 1
            low[u] = min(low[u], dfn[v]); //写法 2
        }
    }
    if(dfn[u] == low[u]) {
        ++_scc;
        int t;
        do {
            t = stk[top--];
            ins[t] = 0;
            scc[t] = _scc;
            scc_sum[_scc] += a[t];
        }while(t != u);
    }
}

写法 1 是严格按照我上述的过程分析定义的 \(low\), 描述了从 \(u\) 出发的可以到达的最浅祖先. 这种的正确性是上面论证过的.

写法 2 是我们的习惯写法. 其中的 \(low(u)\) 代表从 \(u\) 的子树的任意节点以及从它们出发可以一次到达的仍在栈中的节点的时间戳最小值. 我们发现, 它的区别在于, 它对横叉边的处理没有那么干脆利索: 对于 \((u, x)\) 的横叉边更新, 它没有以 \(x\) 所在 SCC 的根(是 \(u\) 的某个祖先, 记作 \(root(x)\))的时间戳作为更新 \(low\) 的值, 而是直接以 \(x\) 的时间戳更新. 这样也是正确的: 因为这一步最重要的是使 \(root(x)\to u\) 上除了 \(root(x)\) 以外的节点认识到自己不是 SCC 的根(这是可以做到的, 因为 \(x\) 的时间戳比它们都小, 所以它们的 \(low\) 会更新地比它们自己更小), 而 \(root(x)\) 本身不需更新 - 它的 \(low\) 的初值就是它自己的时间戳.

为什么会习惯第二种写法呢? 往后看, 因为它可以和其它几个 Tarjan 算法统一.

完整代码

#include <iostream>
#include <iostream>
using namespace std;

constexpr int MAXN = 1e4 + 5;
constexpr int MAXM = 1e5 + 5;

int n, m, a[MAXN];
struct Graph {
    struct Edge {
        int v, nxt;
    }e[MAXM];
    int head[MAXN], cnt;
    void addedge(int u, int v) {
        e[++cnt] = {v, head[u]};
        head[u] = cnt;
    }
}G1, G2;

int dfn[MAXN], low[MAXN], _dfn, stk[MAXN], top, ins[MAXN], scc[MAXN], _scc, scc_sum[MAXN], deg[MAXN], que[MAXN], hd, tl, f[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++_dfn;
    stk[++top] = u;
    ins[u] = 1;
    for(int i = G1.head[u]; i; i = G1.e[i].nxt) {
        int v = G1.e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(ins[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]) {
        ++_scc;
        int t;
        do {
            t = stk[top--];
            ins[t] = 0;
            scc[t] = _scc;
            scc_sum[_scc] += a[t];
        }while(t != u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G1.addedge(u, v);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i);
    for(int u = 1; u <= n; u++)
        for(int i = G1.head[u]; i; i = G1.e[i].nxt) {
            int v = G1.e[i].v;
            if(scc[u] == scc[v]) continue;
            G2.addedge(scc[u], scc[v]);
            deg[scc[v]]++;
        }
    hd = 1; tl = 0;
    for(int i = 1; i <= _scc; i++)
        if(deg[i] == 0) {
            que[++tl] = i;
            f[i] = scc_sum[i];
        }
    while(hd <= tl) {
        int u = que[hd++];
        for(int i = G2.head[u]; i; i = G2.e[i].nxt) {
            int v = G2.e[i].v;
            f[v] = max(f[v], f[u] + scc_sum[v]);
            if(--deg[v] == 0)
                que[++tl] = v;
        }
    }
    int ans = 0;
    for(int i = 1; i <= _scc; i++)
        ans = max(ans, f[i]);
    cout << ans << '\n';
    return 0;
}

求割点和点双连通分量(v-BCC)

题目链接: LG_P3388 割点

题目链接: LG_P8435 点双连通分量

割点是指, 在连通图(或非连通图的一个连通块中), 删去点 \(u\) 及与它相邻的边会使剩余的图不再连通(或连通块个数增多)的点 \(u\).

点双连通分量(v-BCC), 简称点双, 是指一个极大子图满足删去任意一个点, 得到的子图仍然连通.

这个题解讲得非常详细.

展开代码 - P3388

#include <algorithm>
#include <iostream>
using namespace std;

constexpr int MAXN = 2e4 + 5;
constexpr int MAXM = 2e5 + 5;
int n, m;
struct Edge {
    int v, nxt;
}e[MAXM];
int head[MAXN], cnt;
void addedge(int u, int v)  {
    e[++cnt] = {v, head[u]};
    head[u] = cnt;
}

int dfn[MAXN], low[MAXN], _dfn, cut[MAXN];

void tarjan(int u, int fa, int rt) {
    dfn[u] = low[u] = ++_dfn;
    int ch = 0;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        if(!dfn[v]) {
            ch++;
            tarjan(v, u, rt);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                if(u != rt || ch >= 2)
                    cut[u] = 1;
            }
        } else
            low[u] = min(low[u], dfn[v]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addedge(u, v);
        addedge(v, u);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i, 0, i);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        if(cut[i])
            ++ans;
    cout << ans << '\n';
    for(int i = 1; i <= n; i++)
        if(cut[i])
            cout << i << ' ';
    cout << '\n';
    return 0;
}

展开代码 - P8435

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

constexpr int MAXN = 5e5 + 5;
constexpr int MAXM = 4e6 + 5;

int n, m;
struct Edge {
    int v, nxt;
}e[MAXM];
int head[MAXN], cnt;
void addedge(int u, int v) {
    e[++cnt] = {v, head[u]};
    head[u] = cnt;
}

int dfn[MAXN], low[MAXN], _dfn, stk[MAXN], top;
vector<vector<int> > dcc;//v-dcc

void tarjan(int u, int fa, int rt) {
    dfn[u] = low[u] = ++_dfn;
    stk[++top] = u;
    if(u == rt && !head[u]) {
        dcc.push_back(vector<int>{u});
        return ;
    }
    int ch = 0;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa)
            continue;
        if(!dfn[v]) {
            ch++;
            tarjan(v, u, rt);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                dcc.push_back(vector<int>{});
                int t;
                do {
                    t = stk[top--];
                    dcc[(int)dcc.size()-1].push_back(t);
                }while(t != v);
                dcc[(int)dcc.size()-1].push_back(u);
            }
        } else
            low[u] = min(low[u], dfn[v]);
    } 
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        if(u == v)
            continue; //cases that (u, u) and u is size 1
        addedge(u, v);
        addedge(v, u);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i, 0, i);
    cout << dcc.size() << '\n';
    for(const auto &t : dcc) {
        cout << t.size() << ' ';
        for(auto v : t)
            cout << v << ' ';
        cout << '\n';
    }
    return 0;
}

求桥和边双连通分量(e-BCC)

题目链接: LG_P8436 边双连通分量

桥是指, 在连通图(或非连通图的一个连通块中), 删去边 \(e\) 会使剩余的图不再连通(或连通块个数增多)的边 \(e\).

边双连通分量(e-BCC), 简称边双, 是指一个极大子图满足删去任意一条边, 得到的子图仍然连通.

这个题解讲得非常详细

展开代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

constexpr int MAXN = 5e5 + 5;
constexpr int MAXM = 4e6 + 5;

int n, m;
struct Edge {
    int v, nxt;
}e[MAXM];
int head[MAXN], cnt = 1;
void addedge(int u, int v) {
    e[++cnt] = {v, head[u]};
    head[u] = cnt;
}

int dfn[MAXN], low[MAXN], _dfn, cut[MAXM];
int vis[MAXN], _bcc;
vector<int> bcc_con[MAXN];



void tarjan(int u, int toe) {
    dfn[u] = low[u] = ++_dfn;
    for(int i = head[u]; i; i = e[i].nxt) {
        if((i ^ 1) == toe)
            continue;
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u])
                cut[i] = cut[i^1] = 1;
        } else
            low[u] = min(low[u], dfn[v]);
    }
}

void dfs(int u) {
    vis[u] = 1;
    bcc_con[_bcc].push_back(u);
    for(int i = head[u]; i; i = e[i].nxt) {
        if(cut[i])
            continue;
        int v = e[i].v;
        if(vis[v])
            continue;
        dfs(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        addedge(u, v);
        addedge(v, u);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i, 0);
    for(int i = 1; i <= n; i++)
        if(!vis[i]) {
            ++_bcc;
            dfs(i);
        }
    cout << _bcc << '\n';
    for(int i = 1; i <= _bcc; i++) {
        cout << bcc_con[i].size() << ' ';
        for(auto v : bcc_con[i])
            cout << v << ' ';
        cout << '\n';
    }
    return 0;
}