概念：有向图中的一部分点，其中所有点都可以互相到达时，称为强连通分量。
把一个有向图中所有的强连通分量各缩成一个点后，剩下的图中没有环，是一个有向无环图（DAG）。有向无环图拓扑序一定，可以进行图上dp/记忆化搜索等操作而不用担心后效性的问题。
Tarjan算法的流程如下：
（1）按照DFS序（dfn[]）为节点排序，同时维护当前节点能到达的祖先中DFS序的最小值（low[]，初值设为dfn）。
（2）用一个栈维护和当前节点有祖先/后代关系的节点，并记录一个节点是否在栈中（S、inS[]）。
（3）在DFS的过程中如果遇到了在栈中的节点，则可以认定该节点为当前节点的祖先，记录它的DFS序。每一个子节点DFS返回后记录它的最小值并与当前节点最小值取最小。
（4）如果在遍历完所有没有访问过的子节点后这个节点的dfn值还是和low值相等，则可以确定，当前栈中该节点及以上的元素共同组成了一个强连通分量（可以只有一个节点），将其取出栈中。
stack<int> S; // 栈相关信息
bool inS[MaxN];
int dfn[MaxN], stime, low[MaxN]; // Tarjan相关信息（stime指搜索时间）
int blockcnt, belong[MaxN]; // 分量相关信息
vector<int> blocks[MaxN];
void dfs(int u) {
dfn[u] = low[u] = ++stime; // 记录dfs序
S.push(u); // 当前节点入栈
inS[u] = true;
for (node* p = h[u]; p != nullptr; p = p->next) {
int v = p->v; // 取下一个节点
if (dfn[v] == 0) { // 如果下一个节点没有访问过
dfs(v); // 递归
low[u] = min(low[u], low[v]); // low取最小
}
else if (inS[v]) // 如果下一个节点在栈中
low[u] = min(low[u], dfn[v]); // low取与dfn的最小
}
if (dfn[u] == low[u]) { // 如果递归完成后dfn和low还是相等
blockcnt++; // 把当前栈中节点记录到一个块里
int cur;
do {
cur = S.top(); S.pop(); // 出栈
inS[cur] = false;
blocks[blockcnt].push_back(cur); // 记录分量信息
belong[cur] = blockcnt;
} while (cur != u); // 一直出栈直到取出当前节点为止
}
}
强连通分量缩点时，将分量内部的边省去，将分量之间的边加入另一个图中。
node* dag[MaxN];
void shrink() {
for (int u = 1; u <= n; u++) { // 遍历原图中的起始点
for (node* p = h[u]; p != nullptr; p = p->next) { // 遍历从起始点出发的每一条边
int v = p->v;
if (belong[u] != belong[v]) // 如果这条边的起止点不在一个分量里
addedge(belong[u], belong[v], dag); // 就把这条边加到新图中
}
}
}
时间复杂度：DFS\(O(n)\)，缩点\(O(m)\)
例题：P3387 【模板】缩点（强连通分量缩点+记忆化搜索）
/*
DOCUMENT NAME "20180711-luogu3387.cpp"
CREATION DATE 2018-07-11
SIGNATURE CODE_20180711_LUOGU3387
COMMENT 【模板】缩点
*/
#include <cstdlib>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int infinity = 1e8;
const int MaxN = 1e4 + 10, MaxM = 1e5 + 10;
int n, m;
int weight[MaxN];
struct node {
int v;
node* next;
};
node* h[MaxN];
node mem[2 * MaxM], *memtop = mem;
#define ALLOCATE (++memtop)
void addedge(int u, int v, node** h = ::h) {
node* p = ALLOCATE;
p->v = v;
p->next = h[u];
h[u] = p;
}
stack<int> S;
bool inS[MaxN];
int dfn[MaxN], stime, low[MaxN];
int blockcnt, belong[MaxN];
int blockweight[MaxN];
vector<int> blocks[MaxN];
void dfs(int u) {
dfn[u] = ++stime;
low[u] = stime;
S.push(u);
inS[u] = true;
for (node* p = h[u]; p != nullptr; p = p->next) {
int v = p->v;
if (dfn[v] == 0) {
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (inS[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
blockcnt++;
int cnt;
do {
cnt = S.top(); S.pop();
inS[cnt] = false;
blocks[blockcnt].push_back(cnt);
blockweight[blockcnt] += weight[cnt];
belong[cnt] = blockcnt;
} while (cnt != u);
}
}
node* dag[MaxN];
void shrink() {
for (int u = 1; u <= n; u++) {
for (node* p = h[u]; p != nullptr; p = p->next) {
int v = p->v;
if (belong[u] != belong[v])
addedge(belong[u], belong[v], dag);
}
}
}
int ans[MaxN];
int search(int u) {
if (ans[u] != -1)
return ans[u];
else {
ans[u] = 0;
for (node* p = dag[u]; p != nullptr; p = p->next) {
int v = p->v;
ans[u] = max(ans[u], search(v));
}
ans[u] += blockweight[u];
return ans[u];
}
}
int main(int argc, char* argv[]) {
memset(ans, -1, sizeof(ans));
cin >> n >> m;
int u, v, w;
for (int i = 1; i <= n; i++)
cin >> weight[i];
for (int i = 1; i <= m; i++) {
cin >> u >> v;
addedge(u, v);
}
for (int i = 1; i <= n; i++)
if (dfn[i] == 0)
dfs(i);
shrink();
int ans = 0;
for (int i = 1; i <= blockcnt; i++) {
ans = max(ans, search(i));
}
cout << ans << endl;
return 0;
}