Tarjan 学习记录

oymz · 2025-02-11 17:20:31 · 算法·理论

前言

最近在复习 Tarjan，解决了一些之前的疑惑，并有了一些新的启发，想借此记录。

前置知识

打 * 号的不必须要

SCC 的定义
*P3387 【模板】缩点题解

需求

姜远仁老师曾经说过：“因为有问题、题目，所以才需要有数据结构。而不是为了去出题、去考，才有的数据结构。”即，先有需求，才有算法。所以，在学习算法时，我们也要先从需求出发。

P3387 【模板】缩点

对于这题，最重要的就是要用好并处理好“允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。”这个条件。

首先，一眼看出拓扑排序。但是，我们发现，如果直接拓扑排序好像不太可行，需要换一种方法。

我们又可以发现一些性质：

只有在环上的点才有可能被经过多次。即所有点和边只能去一次和所有点和边只不止能去一次的区别只体现在环上。
如果能够经过点 u，那么就能够再经过其所在环上的其他点，最后回到点 u。即可达环上点等价于可达整个环。

由以上两条性质可以得到一个想法。因为性质 1，所以可以考虑把环这个特例扔掉，把环转为点，问题转变为所有点和边只能去一次。但是环上的点不能不要。又因为性质 2 和贪心思想，所以将环变成一个点，点的权值为环上点权值之和。最后，再用拓扑排序求最长路。

需要注意，可能会出现多个环相连的情况，即重环，它会使同时存在于多个环中的点被计算多次。但是，我们可以发现，这样的重环也是一个大环，同样满足上面的性质，所以，可以在转环为点的时候只转尽量大的环，即 SCC。这样就不会有重叠，因为每个点都属于且仅属于一个 SCC。

所以我们目前需要一个算法来求出 SCC（即 Tarjan，但在这里我们要尝试自行设计出它，详解下文）。

创造

先明确一下我们要做的事。造出一个算法用来求出有向图中的所有 SCC，并要求时间复杂度能跑 n = 10^5 的数据。

判定有向图中是否存在环

首先，我们发现求所有 SCC 等价于求所有尽量大的环。这个问题乍一看并不好做，所以，我们可以将问题规约为判定一个有向图中是否存在环。

我们发现如果一个点经过至少一条边后可达自己，那么这个点在环上。至此，已经可以实现。一种方法是进行 DFS 图的遍历，维护对于每个点的还没递归，正在递归与完成递归三种状态的标记。刚抵达一个点，还未修改标记时，如果这个点已经被标记为正在递归，那么说明存在环。因为 DFS 图的遍历中，所有正在递归的点都是可达当前点的点。

时间复杂度 O(n) 级别。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, flag;
int vis[N];
vector<int> g[N];

void dfs(int u) {
    if (vis[u]) {
        if (vis[u] == 2) {
            flag = 1;
        }
        return ;
    }
    vis[u] = 1;
    for (int v : g[u]) {
        dfs(v);
    }
    vis[u] = 2;
}

int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    cout << (flag ? "Yes" : "No");
    return 0;
}

求有向图中所有环

将问题扩展，现在考虑求所有环的问题。我们发现，如果当前点可以判定存在环，那么从前一次递归这个点到现在，这一段中递归的点，就是一个环中的点。多维护一下正在递归的点，每次需要时截取后缀即可。

时间复杂度 O(n ^ 2) 级别。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, flag;
int vis[N];
vector<int> g[N], v;

void dfs(int u) {
    if (vis[u]) {
        if (vis[u] == 2) {
            int pos = 0;
            for (int i = 0; i < v.size(); i++) {
                if (v[i] == u) {
                    pos = i;
                    break;  
                }
            }4
            for (int i = pos; i < v.size(); i++) {
                cout << v[i] << ' ';
            }
            cout << '\n';
        }
        return ;
    }
    v.push_back(u);
    vis[u] = 1;
    for (int v : g[u]) {
        dfs(v);
    }
    v.pop_back();
    vis[u] = 2;
}

int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    return 0;
}

一种特别想法是，将截取完的后缀删掉，但这是不可行的。注意到，这里仍然会有重环，也就是说一段后缀可能会被多个环覆盖。不过，如果是求 SCC，那么这是可行的，因为每个点都属于且仅属于一个 SCC。

求 SCC

现在处理终极目标，求 SCC。相较于上一个，其实就是把求环变成了求尽量大的环。那么一个方向是，使尽量大的环影响普通的环。这个影响可以是许多方面的，如某些值。

我们发现，一个点可达的 dfs 序最小的，且仍在递归的点就是这样。如果这个点就是当前点，说明当前点是当前点所在的 SCC 中第一个被抵达的点。于是，我们要把所有dfs 序比它大的，且不在任意一个 SCC 中的，且当前点可达的点加入当前点所在的 SCC。

要维护的。

dfs 序。int dfn[N];
每个点可达的 dfs 序最小的，且仍在递归的点。int low[N];
每个点所在的 SCC。int f[N];
每个 SCC 所包含的点。vector<int> scc;
所有正在递归的点。stack<int> s;
每个点是正在递归。int vis[N];

#include<bits/stdc++.h>

using namespace std;

const int N = 1e4 + 5, M = 1e5 + 5;

int n, m, pos, cnt;
int dfn[N], low[N], vis[N], f[N], ouput[N];
stack<int> s;
vector<int> g[N], scc[N];

void Pop(int u){
    vis[u] = 0;
    f[u] = cnt;
    scc[cnt].push_back(u);
}

void Tarjan(int u){
    s.push(u);
    vis[u] = 1;
    dfn[u] = low[u] = ++pos;
    for(int v : g[u]){
        if(!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }else if(vis[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(dfn[u] == low[u]){
        cnt++;
        while(s.top() != u){
            Pop(s.top());
            s.pop();
        }
        Pop(s.top());
        s.pop();
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        g[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]){
            Tarjan(i);
        }
    }
    for(int i = 1; i <= cnt; i++){
        sort(scc[i].begin(), scc[i].end());
    }
    cout << cnt << '\n';
    for(int i = 1; i <= n; i++){
        if(!ouput[i]){
            for(int x : scc[f[i]]){
                cout << x << ' ';
                ouput[x] = 1;
            }
            cout << '\n';
        }
    }
    return 0;
}

拓展

P3388 【模板】割点（割顶）
P2169 正则表达式
P1262 间谍网络
P2746 [USACO5.3] 校园网Network of Schools
P2812 校园网络【[USACO]Network of Schools加强版】
P1407 [国家集训队] 稳定婚姻
P7687 [CEOI 2005] Critical Network Lines

如有纰漏，敬请谅解。