题解 P3387 【【模板】缩点】
CodyTheWolf · · 题解
缩点怎么能没有思路简单，代码量少的Kosaraju算法呢OwO
这里简单介绍一下这个算法和自己的一些小研究~
首先我们来回忆一下无向图的连通分量和缩点怎么求：
我们按顺序遍历每个点，对于一个点，如果它没被标记，我们就带入dfs求出它能到的所有点并标记。设某个点为第t次带入dfs被标记的，那它就属于第t个连通分量。同样的，同一次带入dfs的点属于一个连通分量，我们把第t个连通分量看成一个点即完成缩点。设原来点x的点值为a[x]，我们新开一个数组c记录连通分量的值，在第t次dfs时，把c[t]+=a[x]即可得到连通分量的值，再重新用连通分量建图即可。那有向图能这么求嘛QwQ？
我们设两个环A，B。A->B（A可以到B，但B不可以到A，可以理解为两个环只有A有一个点有一条到B的边）。按照无向图的遍历标准，我们分别讨论两个情况：
1.在第t次遍历的时候从B开始遍历：很显然B会标成一个环（强连通分量），因为到不了A而退出，在t+？次的时候遍历到A，A也被标成一个环，这不是很好嘛>w<?
不过，
2.在第t次遍历的时候从A开始遍历，因为A和B可以通过某条边相连，它们会被记成一个连通分量，这是不正确的。不过我们可以从无向图的连通分量中获得灵感：
如果在有向图的遍历时，我们每次都能从A->B这个模型的B出发就好了，这样能保证在有向图中也可以像无向图那样求强连通分量。
幸运的是，我们可以用逆后序来解决这个问题。什么是DFS逆后序？
遍历点x时先遍历其的所有儿子v1,v2,v3。当然v1,v2,v3也是相同的操作， 把所有儿子压入栈后再将自己压入栈。它有什么用？（具体步骤）
1.我们先对原图跑一次DFS逆后序并用栈记录。
2.在（反向图）上（像无向图求连通分量一样）求强连通分量即可
据说这样做事实上是对图进行了一次类似拓扑排序的排序，即DFS逆后序。在反向图上时，配合DFS逆后序，此时的图已经是一张处理过的有向图，可以按照无向图那样跑。
3.像无向图那样缩点，跑DP或者SPFA即可，这里就不细说了，比较简单。这么玄学？
是的，像上面说的A->B模型，可以用这个方法分类讨论试试，结论是正确的，并且可以推广到一个很大的图。但是别着急走，下面才是真正的证明。奇怪的小研究：
在翻书和各种博客的时候，几乎没有提及为什么要用逆后序，所以一直没有想透这个算法，不过知道的确切，简单的步骤和上面的那些玄学证明，跑出来也能AC没什么问题。今天在luogu上打算打一下模板的时候，灵光一闪想试试不用逆后序会怎么样，结果：
？？？？？？？？？？？？？？？？？？？？？？？？
？ Accepted 100 用时: 88ms / 内存: 5320KB ？
？？？？？？？？？？？？？？？？？？？？？？？？
啥？AC了？？还比逆后序快了40msQwQ？？？
就在刚刚脱离了博客和书本，重新思考了一下这个算法：
有向图的问题在于：按照无向图的跑法，我们会像A->B模型那样跑错。但是如果先跑了dfs序（前序也可以），然后再把图反过来，按照这个dfs序，本来能到的环就到不了，起到了限制作用。像刚刚的A->B，如果我们把它反过来变成A<-B，我们用普通的DFS前序按照上面的步骤试试：
1.假设DFS序时从B开始跑，栈顶的元素肯定是A中的点，这时候反向图先跑完A（因为跑不到B），然后再跑B，没有问题。
2.假设DFS序时从A开始跑，栈顶的元素肯定是B中的点，这时候反向图从B到A是可以跑到的，那我们不就跑错了嘛？这个时候先跑A才是对的呀。如果换成逆后序，这个时候栈顶是A，这个时候就没有问题了！！！
把图反过来以后，按照逆后序跑，其实是按照原来的遍历顺序跑（因为是先压入儿子再加入自己，自己一定再上面，访问也优先）。
在反向图跑的时候，原来是正向A->B就跑不了，又因为是逆后序，导致只能从A->B这样跑一条跑不到的路，而不能B->A这样跑！这就把A->B强行变成了一条到不了的边！也就完成了缩点！这也说明了，这道模板题的数据有漏洞，才把前序DFS放了过去XD，等题解通过了就在讨论区@一下管理看看（不过也有可能是蒟蒻我想的不够周全）
CODE(附有详细注释！不先阅读上面文字估计看不懂XD）:
#pragma warning (disable:4996)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e4 + 5, maxm = 1e5 + 5;
int x[maxm], y[maxm];//读入的边暂存数组
int head[maxm], nxt[maxm], v[maxm], w[maxm], cnt;//正图
int rhead[maxm], rnxt[maxm], rv[maxm], rcnt;//逆图
int a[maxn], /*原点的权值*/c[maxn]/*强连通分量的权值*/, dp[maxn], mark[maxn]/*点对应的强连通分量编号*/, stack[maxn]/*栈*/, n, m, t/*dfs1中是逆后序，dfs2中是栈顶*/, ans;
bool vis[maxn];
//建议先从main开始阅读
//正反前向星加边
inline void addline(int x, int y) { v[cnt] = y, nxt[cnt] = head[x], head[x] = cnt++; }
inline void raddline(int x, int y) { rv[rcnt] = y, rnxt[rcnt] = rhead[x], rhead[x] = rcnt++; }
inline void dfs1(int x)//逆后序处理
{
vis[x] = true;
for (int i = head[x]; i != -1; i = nxt[i])
if (!vis[v[i]]) dfs1(v[i]);//先遍历并压入儿子
stack[++t] = x;//最后在压入自己
return;
}
inline void dfs2(int x)//求强连通分量
{
mark[x] = t, c[t] += a[x];//给点x赋予强连通编号t，t在最后会被看出一个点，所以在这先把t的权值求了
for (int i = rhead[x]; i != -1; i = rnxt[i])
if (!mark[rv[i]]) dfs2(rv[i]);//按照无向图跑就行了
return;
}
inline void dfs3(int x)//dp求解（很好理解就不注释了，这也不是本题解的重点）
{
if (dp[x]) return;
for (int i = head[x]; i != -1; i = nxt[i])
{
if (!dp[v[i]]) dfs3(v[i]);
dp[x] = max(dp[x], dp[v[i]]);
}
dp[x] += c[x]; return;
}
int main(void)
{
//以下是初始化和加边
memset(head, -1, sizeof head);
memset(rhead, -1, sizeof rhead);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d %d", &x[i], &y[i]), addline(x[i], y[i]), raddline(y[i], x[i]);
//第一次dfs求图的逆后序
for (int i = 1; i <= n; i++) if (!vis[i]) dfs1(i);
t = 0, cnt = 0;//记得初始化一下
//第二次dfs求强连通分量，从栈顶开始遍历，向无向图那样求连通分量即可
for (int i = n; i >= 1; i--) if (!mark[stack[i]]) t++, dfs2(stack[i]);
//这里开始根据强连通分量重新建图，记得初始化w
memset(head, -1, sizeof(head));
memset(nxt, -1, sizeof(nxt));
memset(vis, 0, sizeof(vis));
//把每个点对应的强连通分量当作点连好，即缩点
for (int i = 1; i <= m; i++) if (mark[x[i]] != mark[y[i]]) addline(mark[x[i]], mark[y[i]]);
//dp过程
for (int i = 1; i <= t; i++) { if (!dp[i]) dfs3(i); ans = max(ans, dp[i]); }
printf("%d\n", ans);
return 0;
}