专栏文章

题解：P3387 【模板】缩点

CColinxu2020
P3387题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mipax73r
此快照首次捕获于
2025/12/03 09:01
3 个月前
此快照最后确认于
2025/12/03 09:01
3 个月前
查看原文

算法介绍

在一个有向图上，定义一个强连通分量（SCC）是指其的一个子图，使得从这个子图中的任意一个点出发，能够到达其他所有点，定义一个极大的强连通分量，是指在这个强连通分量的基础上，任意添加一个点，其全部不是强联通分量。
所谓缩点，是指：将一个有向图中，所有极大的强联通分量用一个点表示，将原图中的边，只保留 SCC 间的边，所得的新的有向图，容易发现新的图是一个 DAG。关于这一步正确性的严格证明，请见结论一与结论二。
这里介绍两种求极大强连通分量的算法，Tarjan 和 Kosaraju，他们具有不同的特点，Tarjan 算法扩展性更强，而 Kosaraju 算法更好理解与记忆。

Tarjan

首先，对于一个联通有向图，我们定义他的 DFS 生成树是指：从连通有向图上任意一点开始遍历，不断 DFS 遍历整个图，但是不经过重复点，途中经过的边所构成的树。对于一个任意的有向图，我们可以对于每个连通块分别求出 DFS 生成树，将所得结果成为 DFS 生成树森林。
由 DFS 生成树森林，我们可以将图中的边分为四类：
  1. 树边：顾名思义，在生成树森林中的边；
  2. 返祖边：由某一点指向他的祖先的边；
  3. 横叉边：搜索过程中遇到的已经访问过的点的边，但祖先除外。
  4. 前向边：搜索过程中遇到子树中的点所产生的边。
如果不考虑跨树边，图中所有边都属于这四类之一。但跨树边实际上是可能存在的，不过，跨树边必然是单向的，否则会合并成为一个树，而这种单向的边是不可能在 SCC 中的，因此对答案没有影响。
在此给出一个结论：如果点 uu 是在 DFS 搜索过程中，遇到的某个 SCC 的第一个节点，那么这个强连通分量的所有节点一定都在搜索树上 uu 的子树中，证明见结论三。
那么，我们可以把每个 SCC 视为搜索树中某个节点的一个子树的一部分，不妨在搜索过程中维护一个栈，存储 SCC 还不确定的点。
Tarjan 算法会对每个点维护两个值，它的 DFS 序和在它的子树中能够回溯到的最早的已经在栈中的结点的 DFS 序，将这两个分别称为 dfnidfn_i 和 lowilow_i。
采用深度优先搜索遍历整棵树，假设 uu 是搜索树上的一个点，vv 是和它有连边的另一个点，维护可能遇到的几种情况：
  1. vv 未被遍历过，此时直接搜索 vv 的子树，并令 lowu←min⁡(lowu,lowv)low_u \gets \min(low_u,low_v) 即可。
  2. vv 已被遍历过，且在栈中，此时直接令 lowu←min⁡(lowu,dfnv)low_u \gets \min(low_u,dfn_v) 即可；
  3. vv 已被遍历，且不在栈中，此时没有任何影响。
对于一个 SCC，容易发现只有第一个被访问过的结点满足 dfnu=lowudfn_u=low_u，不知为何，很多题解直接使用了这个并不显然的结论而不加以证明，证明见下方结论四。因此只需要在回溯时判定如果 dfnu=lowudfn_u=low_u，弹出栈中 uu 上方所有点，并组成一个 SCC 即可。
复杂度为严格线性。

Kosaraju

不妨逆向考虑最后得到的 DAG，假设我们可以通过某种方法求得这个 DAG 的拓扑序，那么显然我们可以按照逆拓扑序逐个遍历每个 SCC，从其中任意一个点开始 DFS，将所有能到达且没有被访问过的点扔到一个 SCC 里，因为不能访问到其他没有被访问过的 SCC 的点。
但我们实际上是做不到这个事情的，考虑一个弱化的版本，我们设其中所有入度为 00 的 SCC 构成的集合为 SS，出度为 00 的集合是 TT，不妨只考虑求 TT，之后再基于 TT 更新新产生的 TT，但 TT 也是很难求的，再次将问题转化，SS 是很好求的，如果我们把这个图的 DFS 搜索树的后缀遍历拿出来，那么最后一个点显然一定是在 SS 中的。
那么我们只要能把 SS 变成 TT 就都做完了，考虑建立反图，显然原图的 SS 就是反图的 TT 然后就做完了。
总结一下算法实现，先 DFS 一遍整个图，求出后缀遍历的反序列，之后对于每个点，在反图上 DFS 一下，将所有点加入当前 SCC 即可。

扩展：SCC 标号与拓扑排序

Tarjan

考察 Tarjan 中被最优先处理的是什么样的点，发现显然就是那些没有出度的点，而这和拓扑排序反全是反过来的。而又因为我们的 SCC 编号是按顺序排的，所以本质上相当于把拓扑序反了过来。
因此，SCC 编号等于逆拓扑序。

Kosaraju

考察我们上面提到的算法流程，因为我们最先访问的点是 SS 中的点，也就是没有入度的点，这和拓扑序完全相同，因此当使用 Kosaraju 算法时：
SCC 编号等于拓扑序编号。

正确性证明

因为是模板题所以对于一些比较显然的结论也写了证明 qwq。

结论一

结论

一个有向图中，所有极大强连通分量不交。

证明

反证，假设第一个极大强连通分量包含的点集为 SS，第二个包含的点集为 TT，由条件可得 S∩T≠∅S \cap T \neq \emptyset，从 S∩TS \cap T 中任选出一个节点 xx，由定义可得 SS 中的所有点都能到达 xx，xx 也能到达所有点，TT 具有相同的性质。
由此，对于 SS 中的一个点 uu 和 TT 中的一个点 vv，必然存在路径 u→x→vu \rightarrow x \rightarrow v 和 v→x→uv \rightarrow x \rightarrow u，因此，S∪TS \cup T 也是一个强连通分量，且比 SS 更大，证毕。

结论二

结论

一个有向图中，如果将所有强连通分量缩成一个点，则这个图一定无环。

证明

反证，假设这个图中有环，环上的点代表的 SCC 组成的集合为 SS，则从 SS 中任取两个集合，从这两个集合中分别取一个元素 x,yx,y，必然存在一个先从 xx 到环上，绕环一周，再到 yy 所在 SCC，最后到达 yy 的路径，因此 SS 应在同一个 SCC 中，证毕。

结论三

结论

如果点 uu 是在 DFS 搜索过程中，遇到的某个 SCC 的第一个节点，那么这个强连通分量的所有节点一定都在搜索树上 uu 的子树中

证明

反证，假设存在一个节点 vv 在 SCC 中，但不在 uu 的子树中，由定义可得必然存在 uu 到 vv 的路径，而又因为 vv 不在 uu 的子树中，所以这条路径一定经过了离开 uu 子树的边，考察这个边可能是哪些种类，显然不可能是树边，因为树边只能指向儿子节点，同理也不能是前向边，因此只能是返祖边或横叉边，而对于这两种情况，通过定义可得这条边的另一端已经被访问过了，由边的类型，vv 一定在 uu 之前被访问，所以 uu 不是最早被访问的节点，矛盾。

结论四

结论

一个点 uu 是他所在 SCC 中第一个被遍历的点，当且仅当 lowu=dfnulow_u=dfn_u。

证明

必要性

下面证明，如果 uu 不是第一个被遍历的点，那么 lowu≠dfnulow_u \neq dfn_u，假设 vv 是第一个被遍历的点，由结论三得 uu 在 vv 的子树中（而且不是 vv），因此 dfnv<dfnudfn_v \lt dfn_u，由 lowlow 的定义，由 lowu≤dfnvlow_u \leq dfn_v，由不等式的传递性，有 lowu<dfnulow_u \lt dfn_u，因而 lowu<dfnulow_u \lt dfn_u。

充分性

考虑反证法，假设一个点是第一次遍历到的点，而且 lowu≠dfnulow_u \neq dfn_u，显然有 lowu≤dfnulow_u \leq dfn_u，因此 lowu<dfnulow_u \lt dfn_u，根据定义，可得此时存在一条从 uu 子树中某个节点 vv（注意这里的 u,vu,v 和上一条证明中的不同）到某个节点 ww 的边，使得 ww 在栈中，而且 dfnw=lowu<dfnudfn_w =low_u \lt dfn_u，因此 ww 一定是 uu 的祖先，因而，存在一条从 ww 到 vv 的路径（w→u→vw \rightarrow u \rightarrow v），同时，存在一条从 vv 到 ww 的路径，这代表 ww 也在 SCC 中，而 ww 在 uu 之前被遍历，这和假设矛盾，证毕。

代码实现

Tarjan:
CPP
#include<iostream>
#include<vector>
#include<stack>
#include<set>
using namespace std;

const int maxn=1e4+10;
int n,m,ai[maxn],dfn[maxn],low[maxn],instk[maxn],tim,pri[maxn],dp[maxn],scccnt,scc[maxn];
vector<int> grp[maxn],newgrp[maxn]; stack<int> stk;
set<pair<int,int>> antidup;

void tarjan(int x){
    dfn[x]=low[x]=++tim; instk[x]=true; stk.push(x);
    for(auto y:grp[x]){
        if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]); // 题解情况一
        else if(instk[y])low[x]=min(low[x],dfn[y]); // 题解情况二
    }
    if(low[x]==dfn[x]){
        scccnt++;
        while(stk.top()!=x)pri[scccnt]+=ai[stk.top()],scc[stk.top()]=scccnt,instk[stk.top()]=false,stk.pop();
        pri[scccnt]+=ai[x]; scc[x]=scccnt; stk.pop(); instk[x]=false;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>ai[i];
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        grp[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:grp[u])if(scc[u]!=scc[v]){
        if(antidup.count({scc[u],scc[v]}))continue; // 防止重边
        antidup.insert({scc[u],scc[v]});
        newgrp[scc[u]].push_back(scc[v]); // 建新图
    }
    for(int i=1;i<=scccnt;i++)dp[i]=pri[i];
    for(int i=scccnt;i>=1;i--){
        for(auto x:newgrp[i])dp[x]=max(dp[x],dp[i]+pri[x]); // 拓扑序上 DP
    }
    int ans=0;
    for(int i=1;i<=scccnt;i++)ans=max(ans,dp[i]);
    cout<<ans<<endl;
}
Kosaraju：
CPP
#include<iostream>
#include<vector>
#include<stack>
#include<set>
using namespace std;

const int maxn=1e4+10;
int n,m,ai[maxn],pri[maxn],dp[maxn],scccnt,vis[maxn],scc[maxn];
vector<int> grp[maxn],rgrp[maxn],newgrp[maxn]; stack<int> stk;
set<pair<int,int>> antidup;

void dfs1(int x){
    vis[x]=true;
    for(auto y:grp[x])if(!vis[y])dfs1(y);
    stk.push(x);
}
void dfs2(int x, int no){
    scc[x]=no; pri[no]+=ai[x];
    for(auto y:rgrp[x])if(!scc[y])dfs2(y, no);
}
void kosaraju(){
    for(int u=1;u<=n;u++)for(auto v:grp[u])rgrp[v].push_back(u);
    for(int i=1;i<=n;i++)if(!vis[i])dfs1(i);
    for(int i=1;i<=n;i++,stk.pop())if(!scc[stk.top()])dfs2(stk.top(),++scccnt);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>ai[i];
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        grp[u].push_back(v);
    }
    kosaraju();
    for(int u=1;u<=n;u++)for(auto v:grp[u])if(scc[u]!=scc[v]){
        if(antidup.count({scc[u],scc[v]}))continue; // 防止重边
        antidup.insert({scc[u],scc[v]});
        newgrp[scc[u]].push_back(scc[v]); // 建新图
    }
    for(int i=1;i<=scccnt;i++)dp[i]=pri[i];
    for(int i=1;i<=scccnt;i++){
        for(auto x:newgrp[i])dp[x]=max(dp[x],dp[i]+pri[x]); // 拓扑序上 DP
    }
    int ans=0;
    for(int i=1;i<=scccnt;i++)ans=max(ans,dp[i]);
    cout<<ans<<endl;
}

例题

P2341 受欢迎的牛

考察什么样的牛可能成为受欢迎的，考虑把图缩点，缩点后的 DAG 必须是联通的，之后，在 DAG 上找到所有入度为 00 的 SCC，这些 SCC 里的所有点都可以，因为他们能通向所有点，注意特判有 ≥2\geq 2 个入度为 00 的点即可。

P3387 [模板]缩点

先考虑 DAG 上的情况，可以在拓扑序上 DP，设 fif_i 代表 ii 开始的最长路，答案为 max⁡fi\max f_i，转移为 fi=max⁡{fj}+aif_i=\max\{f_j\}+a_i，其中 ii 和 jj 有连边。、
考虑优化，注意到一个 SCC 内走一个就会把所有的都走了，于是考虑缩点，在缩点得到的 DAG 上 DP 即可，特别的，将每个新点的权值赋为所有其中的点的权值和即可。
P3627 和这题本质相同。

P2194 HXY 烧情侣

显然对于 SCC 只需要烧一次，而且一定会回来，而对于不同 SCC，烧了就回不来了，因此不符合题意，综上所述，只需要缩点后对于每个 SCC 求出其中最小点权，再求和即可。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...