题解：P3387 【模板】缩点

lw393 · 2025-05-07 21:09:40 · 题解

tarjan 题解

算法讲解

写这道题，一定要会一个能求强连通分量（SCC）的算法！这里就介绍 tarjan。

~~我知道~~ tarjan 有很多，但是这里只讲在有向图中求强连通分量的一种。

先言 scc：scc（强连通分量）是指一个图中的某个子图。这个子图满足性质：任意两个节点可以通过子图中的边互相到达。

再谈 dfs 生成树（我们使用 tarjan 就是建立在这种生成树之上的）。

它是以图上 dfs 遍历走过的边建出来的一棵树。显然地，它并不唯一，但是任意图的任意 dfs 生成树对于 tarjan 的正确性并不影响分毫。

借助图来理解：

一棵 dfs 生成树有这样几种边（不一定全都有，反正我给出来的全都有）（取名参照 oi-wiki）：

树边（黑色）：是生成树上的边，每次 dfs 遍历到未访问的点时，就会建一条树边。
返祖边（红色）：是生成树外原图中一个节点向它的祖先连的边。
横向边（蓝色）：一样也是生成树外原图中的一条边。它由一个节点连向非自己在生成树上祖先的节点，
前向边（绿色）：是一个节点连向其子树内的节点的边。

然后正式开始 tarjan。

我们寻找 dfs 生成树与 scc 的关系。

我们发现：如果某个节点是原图中某个 scc 的在 dfs 树中的 dfs 序最小的，则这一整个 scc 都在这个节点的子树内。

通过这个性质，我们可以将一个 scc 在这个树上的一棵子树，在 dfs 过程中维护一个栈，将未处理的节点在栈中处理。

我们在 tarjan 中需维护：

每个节点的 dfs 序（命名为 dfn）；
在这个节点能够回溯到的最早在栈中的节点（命名为 low）。

然后怎么判断是否有一个 scc 彻底遍历完了呢？简单！由于上文的发现，我们知道一个点的 dfn 值等于 low 值，则说明遍历完了。

正确性分析

将上面的性质做如下证明：

反证法：假设节点 v 在一个强连通分量中，设这个 scc 中最早出现在 dfs 遍历中的节点为 u。若 v 不在以 u 为根的字数内，则 u, v 之间必有一条离开子树的路径。这种路径中的边必有横叉边或返祖边，然而这两种边都要求指向的节点已访问过的，与 v 不在 u 为根的字数内矛盾。

代码实现

const int N = 1e4 + 5;
vector<int>G[N];//邻接表
int dfn[N], low[N], ins[N], num; //ins 为处理节点是否在栈中的辅助数组。
stack<int>s;

int scc[N], scc_cnt;//记录 scc 编号

void tarjan(int u){
  dfn[u] = ins[u] = ++num, ins[u] = 1;
  s.push(u);
  for(auto v : G[u]){
    if(!dfn[v]) { tarjan(v); low[u] = min(low[v], low[u]); } //dfs 搜索
    else if(ins[v]) { low[u] = min(low[u], dfn[v]); } //更新 low 值
  }
  if(dfn[u] == low[u]){ //说明这个 scc 到头了
    int v; scc_cnt++;
    do{
      v = s.top();
      s.pop();
      scc[v] = scc_cnt, ins[v] = 0;
    }while(u != v);
  }
}

时间复杂度看得出来是 O(n+m)。

这就是一个完整的 tarjan 模板代码。

本题做法

然而对于这道题目不够。这道题目点带点权，要求最长路。我们还要处理一个 scc 中所有点的点权的和值。同时我们将一个 scc 看作一个点，重新建一个图，而这个图没有 scc，所以这个图上一定无环，是一个 DAG，我们直接在图上跑一遍拓补，利用它来进行 dp 即可。

参考代码（无注释）：

#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;

vector<int>G[N], G_scc[N];

int val[N];

int dfn[N], low[N], ins[N], num;
int scc[N], w[N], scc_cnt;
stack<int>s;

void tarjan(int u){
    dfn[u] = low[u] = ++num;
    s.push(u);
    ins[u] = 1;
    for(auto v : G[u]){
        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]){
        int v;
        scc_cnt++;
        do{
            v = s.top();
            s.pop();
            ins[v] = 0, scc[v] = scc_cnt;
            w[scc_cnt] += val[v];
        }while(v != u);
    }
}

int in[N], dp[N];

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> val[i];
    }
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++){
        for(auto v : G[u]){
            if(scc[u] == scc[v]) continue;
            G_scc[scc[u]].push_back(scc[v]);
            in[scc[v]]++;
        }
    }
    queue<int>q;
    for(int i = 1; i <= scc_cnt; i++){
        if(in[i] == 0) q.push(i);
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto v : G_scc[u]){
            dp[v] = max(dp[v], dp[u] + w[u]);
            in[v]--;
            if(in[v] == 0) q.push(v);
        }
    }
    int ans = 0;
    for(int i = 1; i <= scc_cnt; i++){
        ans = max(ans, dp[i] + w[i]);
    }
    cout << ans << '\n';
}

int main(){
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}