强连通分量（SCC）与缩点

前面这篇文章着重介绍了 Tarjan 算法找强连通分量的方法。
此文章着重介绍缩点。寻找 SCC 的方法依然是 Tarjan 算法。

缩点

温习一下缩点的定义：把强连通分量看成是一个大点，保留那些不在强连通分量里的边，这样的图就是缩点后的图。

还是拿上一篇文章的例子来说，缩点后的图长这样

跑一遍这样的代码，把在同一个 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;
}