前面这篇文章着重介绍了 Tarjan 算法找强连通分量的方法。 此文章着重介绍缩点。寻找 SCC 的方法依然是 Tarjan 算法。
缩点
温习一下缩点的定义：把强连通分量看成是一个大点，保留那些不在强连通分量里的边，这样的图就是缩点后的图。
看图就明白，缩点后的图要保留所有不在分量里的边，而且缩点后的图是一个有向无环图(DAG)，也就是说可以进行拓扑排序。
还是拿上一篇文章的例子来说，缩点后的图长这样
跑一遍这样的代码，把在同一个 SCC 里的点染成同色。
if (dfn[v] == low[v]) {
sccnt++; // 每找到一个强连通分量，强连通分量序号 +1
int u = sta.top();
do {
u = sta.top();
vis[u] = false;
sta.pop();
color[u] = sccnt; // color 数组存储每个点所在的 SCC 序号，类似于染上相同的颜色
} while (v != u);
}运行以上代码后，3 个 SCC 的编号为
存储缩点后的图
接下来进入正题：如何储存缩点后的图？
在一般的图论题中，我们在读入数据时不会储存输入的数据，但这次不一样，我们需要储存输入的数据，以便再次利用这些点的关系。 所以使用数组存输入的数据就好。
在建立邻接表储存缩点后的图时，判断这些输入的点是否在同一个 SCC 中，如果不在就连边。
代码
for (int i = 1; i <= m; i++)
if (color[from[i]] != color[to[i]])
add(color[from[i]], color[to[i]]);其中 from 和 to 是用来储存输入数据的数组。
如果不需要原来的图，可以用 memset 函数初始化邻接表和 head 数组
（以前天真地认为结构体不能用 memset 进行初始化，后来才发现可以）
关于缩点这道模板题
洛谷上的模板题虽然叫缩点，但还需要找出一条路径使点权值和最大。 因为 SCC 中点可以互相到达，所以需要缩点使图变成一个有向无环图(DAG)，SCC 内所有点权和即为缩点后该点的点权。
可以考虑用记忆化搜索（但是我太蒟蒻了不会记忆化搜索）。
还可以使用一些其(qi)他(yin)方(ji)法(qiao)。
通过魔改 SPFA 等最短路算法，把它修改成求点权最长路的算法（本质上就是把松弛变成扩张，把边权变成点权）。
初始化时要把自身所在点点权加上（不要初始化为 0），dis 数组要初始化为一个极小值。
把原来的判断 dis[v] > dis[u] + edge[i].cost，魔改成 dis[v] < dis[u] + siz[v]，其中 siz 数组存储了缩点后的点权。
这样跑一遍魔改后的 SPFA(LPFA)，dis 数组中最大的数即为从源点出发点权和最大的路径上的点权和（说得有点绕）。
为了找到最优解，需要把每个点作为源点跑一遍魔改版 SPFA，像这样找出全局的最大值，这个值即为所求。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxN = 2e5 + 3;
struct Edge {
int next, to;
} edge[maxN];
int head[maxN], dfn[maxN], low[maxN];
int color[maxN], val[maxN], siz[maxN];
int from[maxN], to[maxN], dis[maxN];
bool vis[maxN], used[maxN];
int cnt, tot, sccnt, ans, n, m;
stack<int> sta;
template<typename Tp> void read(Tp &x) {
char c = getchar();
x = 0;
while (!isdigit(c)) c = getchar();
do {
x = x * 10 + (c ^ 48);
c = getchar();
} while (isdigit(c));
}
void add(int from, int to) {
edge[++cnt].next = head[from];
edge[cnt].to = to;
head[from] = cnt;
}
void tarjan(int v) {
dfn[v] = low[v] = ++tot;
sta.push(v);
vis[v] = true;
for (int i = head[v]; ~i; i = edge[i].next) {
int u = edge[i].to;
if (!dfn[u]) {
tarjan(u);
low[v] = min(low[v], low[u]);
} else if (vis[u])
low[v] = min(low[v], dfn[u]);
}
if (dfn[v] == low[v]) {
sccnt++;
int u = sta.top();
do {
u = sta.top();
vis[u] = false;
sta.pop();
color[u] = sccnt;
siz[sccnt] += val[u];
} while (v != u);
}
}
void spfa(int s) {
queue<int> que;
memset(used, false, sizeof(used));
memset(dis, 0, sizeof(dis));
que.push(s);
dis[s] = siz[s];
used[s] = true;
while (!que.empty()) {
int u = que.front();
que.pop();
used[u] = false;
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (dis[v] < dis[u] + siz[v]) {
dis[v] = dis[u] + siz[v];
if (!used[v]) {
used[v] = true;
que.push(v);
}
}
}
}
for (int i = 1; i <= sccnt; i++)
ans = max(ans, dis[i]);
}
int main() {
memset(head, -1, sizeof(head));
read(n), read(m);
for (int i = 1; i <= n; i++) read(val[i]);
for (int i = 1; i <= m; i++) {
read(from[i]), read(to[i]);
add(from[i], to[i]);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
memset(head, -1, sizeof(head));
memset(edge, 0, sizeof(edge));
for (int i = 1; i <= m; i++)
if (color[from[i]] != color[to[i]])
add(color[from[i]], color[to[i]]);
for (int i = 1; i <= sccnt; i++) spfa(i);
printf("%d\n", ans);
}Tarjan 求割点
割点：无向连通图中，删除掉某点及其所连边使整幅图不连通。
和 Tarjan 求 SCC 差不多，进行搜索时要传两个参，一个是自身，一个是祖先。
如果自身是树根，且有两个或以上的子树，那么它自身一定是割点。（去掉后两个子树不连通） 如果自身不是树根，但其儿子的 low 值大于这个点的 dfn 值，那么它也一定是割点。（子树中没有能够直接到达祖先的点）
代码
void tarjan(int v, int fa) {
low[v]= dfn[v] = ++tot;
int ch = 0;
for (int i = head[v]; ~i; i = edge[i].next) {
int u = edge[i].to;
if (!dfn[u]) {
tarjan(u, fa);
low[v] = min(low[v], low[u]);
if (low[u] >= dfn[v] && v != fa) cut[v] = true;
if (v == fa) ch++;
}
low[v] = min(low[v], dfn[u]);
}
if (ch >= 2 && v == fa) cut[v] = true;
}