题解：P3387 【模板】缩点

· · 题解

算法介绍

在一个有向图上，定义一个强连通分量（SCC）是指其的一个子图，使得从这个子图中的任意一个点出发，能够到达其他所有点，定义一个极大的强连通分量，是指在这个强连通分量的基础上，任意添加一个点，其全部不是强联通分量。

所谓缩点，是指：将一个有向图中，所有极大的强联通分量用一个点表示，将原图中的边，只保留 SCC 间的边，所得的新的有向图，容易发现新的图是一个 DAG。关于这一步正确性的严格证明，请见结论一与结论二。

这里介绍两种求极大强连通分量的算法，Tarjan 和 Kosaraju，他们具有不同的特点，Tarjan 算法扩展性更强，而 Kosaraju 算法更好理解与记忆。

Tarjan

首先，对于一个联通有向图，我们定义他的 DFS 生成树是指：从连通有向图上任意一点开始遍历，不断 DFS 遍历整个图，但是不经过重复点，途中经过的边所构成的树。对于一个任意的有向图，我们可以对于每个连通块分别求出 DFS 生成树，将所得结果成为 DFS 生成树森林。

由 DFS 生成树森林，我们可以将图中的边分为四类：

  1. 树边：顾名思义，在生成树森林中的边；
  2. 返祖边：由某一点指向他的祖先的边；
  3. 横叉边：搜索过程中遇到的已经访问过的点的边，但祖先除外。
  4. 前向边：搜索过程中遇到子树中的点所产生的边。

如果不考虑跨树边，图中所有边都属于这四类之一。但跨树边实际上是可能存在的，不过，跨树边必然是单向的，否则会合并成为一个树，而这种单向的边是不可能在 SCC 中的，因此对答案没有影响。

在此给出一个结论：如果点 u 是在 DFS 搜索过程中，遇到的某个 SCC 的第一个节点，那么这个强连通分量的所有节点一定都在搜索树上 u 的子树中，证明见结论三。

那么，我们可以把每个 SCC 视为搜索树中某个节点的一个子树的一部分，不妨在搜索过程中维护一个栈，存储 SCC 还不确定的点。

Tarjan 算法会对每个点维护两个值，它的 DFS 序和在它的子树中能够回溯到的最早的已经在栈中的结点的 DFS 序，将这两个分别称为 dfn_i 和 low_i。

采用深度优先搜索遍历整棵树，假设 u 是搜索树上的一个点，v 是和它有连边的另一个点，维护可能遇到的几种情况：

对于一个 SCC，容易发现只有第一个被访问过的结点满足 dfn_u=low_u，不知为何，很多题解直接使用了这个并不显然的结论而不加以证明，证明见下方结论四。因此只需要在回溯时判定如果 dfn_u=low_u，弹出栈中 u 上方所有点，并组成一个 SCC 即可。

复杂度为严格线性。

Kosaraju

不妨逆向考虑最后得到的 DAG，假设我们可以通过某种方法求得这个 DAG 的拓扑序，那么显然我们可以按照逆拓扑序逐个遍历每个 SCC，从其中任意一个点开始 DFS，将所有能到达且没有被访问过的点扔到一个 SCC 里，因为不能访问到其他没有被访问过的 SCC 的点。

但我们实际上是做不到这个事情的，考虑一个弱化的版本，我们设其中所有入度为 0 的 SCC 构成的集合为 S，出度为 0 的集合是 T，不妨只考虑求 T，之后再基于 T 更新新产生的 T，但 T 也是很难求的，再次将问题转化，S 是很好求的，如果我们把这个图的 DFS 搜索树的后缀遍历拿出来，那么最后一个点显然一定是在 S 中的。

那么我们只要能把 S 变成 T 就都做完了，考虑建立反图，显然原图的 S 就是反图的 T 然后就做完了。

总结一下算法实现，先 DFS 一遍整个图，求出后缀遍历的反序列，之后对于每个点，在反图上 DFS 一下，将所有点加入当前 SCC 即可。

扩展：SCC 标号与拓扑排序

Tarjan

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

因此，SCC 编号等于逆拓扑序。

Kosaraju

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

SCC 编号等于拓扑序编号。

正确性证明

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

结论一

结论

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

证明

反证，假设第一个极大强连通分量包含的点集为 S，第二个包含的点集为 T，由条件可得 S \cap T \neq \emptyset，从 S \cap T 中任选出一个节点 x，由定义可得 S 中的所有点都能到达 x，x 也能到达所有点，T 具有相同的性质。

由此，对于 S 中的一个点 u 和 T 中的一个点 v，必然存在路径 u \rightarrow x \rightarrow v 和 v \rightarrow x \rightarrow u，因此，S \cup T 也是一个强连通分量，且比 S 更大，证毕。

结论二

结论

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

证明

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

结论三

结论

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

证明

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

结论四

结论

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

证明

必要性

下面证明，如果 u 不是第一个被遍历的点，那么 low_u \neq dfn_u，假设 v 是第一个被遍历的点，由结论三得 u 在 v 的子树中（而且不是 v），因此 dfn_v \lt dfn_u，由 low 的定义，由 low_u \leq dfn_v，由不等式的传递性，有 low_u \lt dfn_u，因而 low_u \lt dfn_u。

充分性

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

代码实现

Tarjan:

#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：

#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 上找到所有入度为 0 的 SCC，这些 SCC 里的所有点都可以，因为他们能通向所有点，注意特判有 \geq 2 个入度为 0 的点即可。

P3387 [模板]缩点

先考虑 DAG 上的情况，可以在拓扑序上 DP，设 f_i 代表起点到 i 的最长路，答案为 \max f_i，转移为 f_j=\max\{f_i\}+a_i，其中 i 和 j 有连边。、

考虑优化，注意到一个 SCC 内走一个就会把所有的都走了，于是考虑缩点，在缩点得到的 DAG 上 DP 即可，特别的，将每个新点的权值赋为所有其中的点的权值和即可。

P3627 和这题本质相同。

P2194 HXY 烧情侣

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