Shrink-point-algorithm

缩点

定义

缩点，就是把一张有向有环图中的环缩成一个个点，形成一个有向无环图。同时将合并的几个点的权值相加。

写在前面：当你看到题目不是DAG(有向无环图)时，基本就可以考虑缩点或者割点了。

实现方式——Tarjan算法

说到Tarjan算法，其实我们并不陌生，之前在LCA那篇博客就曾经介绍过这个算法，今天借着介绍缩点算法我们来具体介绍一下Tarjan算法(当然Tarjan算法和并查集结合也是常见套路，如LCA~)。

Tarjan算法定义

Tarjan算法可以求出一个有向图中的强连通分量的个数，同时还可以将强连通分量改造为一个点，也就是所谓的“缩点”。

前置知识

强连通分量

强连通分量（或者极大连通子图），指的是在一个子图中，所有点能够两两互达，且再加入新的点时将破坏连通性。特别要注意的是，一个点可以被认为是一个强连通分量。

dfs过程产生的边

在tarjan算法的dfs过程中，会产生以下四种边（默认x->y）：

• 树枝边：x是y的父节点
• 前向边：x是y的祖先结点
• 后向边：y是x的孩子节点
• 横叉边：连接到其他连通分量的边

算法

时间戳

Tarjan算法引入了“时间戳”的概念。具体来讲，在dfs每一个点时，将会赋予每一个点一个“时间点”，也就是维护dfn。其次，维护一个low，表示当前这个点和它的子树返祖边和横插边能连到的还没出栈的dfn最小的点。

tarjan算法的两个核心数组：dfn和low，同样也需要一个栈，辅助存储强连通分量。
dfn是“时间戳”，dfn[i]说明i点在什么时间被遍历的，即i点的进入时间。
low[i]是i可回溯到的最早时间戳的点的时间戳，即从i点出发，所能访问到的最早的进入时间，默认值为dfn[i]。
举个例子：如果i到j有一条路径，j到i也有一条路径，那么就使 i -> j -> i 的环中所以点中 low 变为最早时间戳 并入栈，打上在栈内的标记in。

过程

在dfs的过程中维护一个栈，每个点第一次访问时就将其加入栈中。当这个点的所有后继节点遍历完毕时，如果这个点的dfn==low，则这个点是这个强连通分量里面dfs树的最高的点。于是，可以将栈中的点一个一个出栈，直到当前这个点也出栈为止。

当dfn[u]==low[u]时，表明u一定是环上的一点，且环上的其他点就是u的子树。原因如下：

low[x] = dfn[x] = ++id;
low[x] = min(low[x], low[v]);

我截取了两句代码，第一句是对点x的low，dfn的初始化。在之后的操作中,low[x]始终取自己子树low[v]的较小值，那么什么情况会使得dfn[u]又“重新”和low[u]相等呢，就是在u的子树中有一条边（就是博客1中的后向边）直接指回了u。这样不就是形成了一个环了吗？

在遍历一个点的子树过程中，也需要判断后继顶点是否遍历过。简单来说，当后继顶点遍历过（而且在栈里面时），则将这个点的low和后继顶点的low取最小，否则直接dfs下去，再更新low。

int dfn[N], low[N], id;
stack<int> st;//由于是递归，stack要定义在函数外
void tarjan(int x) {//求强连通分量，缩点
    low[x] = dfn[x] = ++id;//id表示时间戳，所以每次调用自动累加
    st.push(x);
    book[x] = 1;
    for (int k = g.head[x]; k != -1; k = g.e[k].link) {//搜索相连节点
        int v = g.e[k].to;
        if (!dfn[v]) {//没搜索过
            tarjan(v);
            low[x] = min(low[x], low[v]);//更新所能到的上层节点
        } else if (book[v]) {
            low[x] = min(low[x], low[v]);//在队中 找到栈中最上端的节点
            //dfn是栈中编号或时间戳，如果s在栈中，则x到栈中最上端节点为dfn[s]
        }
    }
    if (dfn[x] == low[x]) {//找到了一个强联通分量，开始弹栈，直到弹到当前这一个点为止
        while (!st.empty()) {
            sd[st.top()] = x;// 染色,相当于对每一组强连通分支进行编号
            book[st.top()] = 0;
            if (x == st.top()) {
                st.pop();//即使条件满足也是要出栈的
                break;
            }
            g.p[x].val += g.p[st.top()].val;//连通分支的值合并(变环为点)
            st.pop();
        }
    }
}

在遍历完之后，还有一个很重要的步骤——存储已经缩点后的新图。

如果原图一条边上两点属于不同的强连通分量，则两个强连通分量相连，就可以对这两个分量连接

for (int i = 1; i <= m; i++) {
    int x = sd[g.e[i].from];
    int y = sd[g.e[i].to];
    if (x != y) {//不属于同一分量(还记得之前的染色吗)
        ed[++s].link = h[x];
        ed[s].to = y;
        ed[s].from = x;
        h[x] = s;
        ind[y]++;
    }//邻接表存储重新形成新的图
}

后言

在上面的代码中，实际上tarjan算法也创建了一个新的图，这个图中每一个顶点都是原来图中的强连通分量。也就是说，现在这个新的图不再存在回路，是一个DAG。因此，这个新的图可以执行原先不能的操作，比如拓扑排序等等。这样的操作就可以叫做缩点。

模板题

【模板】缩点

【模板】缩点

题目描述

给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式

第一行两个正整数 $n,m$

第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。

第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。

输出格式

共一行，最大的点权之和。

样例 #1

样例输入 #1

2 2
1 1
1 2
2 1

样例输出 #1

2

提示

对于 $100%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，$0\le a_i\le 10^3$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 200007
#define N 20007
#define INF 0x3f3f3f3f
#define mod 99999997
#define ll long long
#define db double
#define pii pair<int, int>
int n, m;
typedef struct edge {
    int from, to, link;
    int id, val;
} Edge;
typedef struct node {
    int val;
} Node;
typedef struct graph {
    int head[N];  
    int node_num = 0;
    Node p[N];
    int edge_num = 0;
    Edge e[M];
} Graph;
Graph g;
Edge ed[M];//新图的
int s, h[N];//新图的边数和头结点
int book[N], sd[N];
void add_edge(int from, int to) {
    g.e[++g.edge_num].to = to;
    g.e[g.edge_num].from = from;
    g.e[g.edge_num].link = g.head[from];
    g.head[from] = g.edge_num;
}
int dfn[N], low[N],id;
stack<int> st;
void tarjan(int x) {
    low[x] = dfn[x] = ++id;
    st.push(x);
    book[x] = 1;
    for (int k = g.head[x]; k != -1; k = g.e[k].link) {
        int v = g.e[k].to;
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min(low[x], low[v]);
        } else if (book[v]) {
            low[x] = min(low[x], low[v]);
        }
    }
    if (dfn[x] == low[x]) {
        while (!st.empty()) {
            sd[st.top()] = x;
            book[st.top()] = 0;
            if (x == st.top()) {
                st.pop();
                break;
            }
            g.p[x].val += g.p[st.top()].val;
            st.pop();
        }
    }
}
int ind[N], f[N];
int topological_sort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0 && sd[i] == i) {
            //之后拓扑排序时用sd[i]==i保证这个点存在于新图
            q.push(i);
            f[i] = g.p[i].val;
        }
    };
    while (!q.empty()) {
        int rhs = q.front();
        q.pop();
        for (int i = h[rhs]; i; i = ed[i].link) {
            int u = ed[i].to;
            ind[u]--;
            if (ind[u] == 0)
                q.push(u);
            f[u] = max(f[u], f[rhs] + g.p[u].val);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f[i]);//这里用dp维护最大值
        cerr << f[i] << endl;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    memset(g.head, -1, sizeof(g.head));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> g.p[i].val;
    }
    int u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        add_edge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        int x = sd[g.e[i].from];
        int y = sd[g.e[i].to];
        if (x != y) {
            ed[++s].link = h[x];
            ed[s].to = y;
            ed[s].from = x;
            h[x] = s;
            ind[y]++;
        }
    }
    cout << topological_sort();
    return 0;
}