Tarjan 算法求强连通分量

概念：有向图中的一部分点，其中所有点都可以互相到达时，称为强连通分量。

把一个有向图中所有的强连通分量各缩成一个点后，剩下的图中没有环，是一个有向无环图（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;
}