可能更好的阅读体验

相关链接

相关概念：https://oi-wiki.org/graph/concept/

题单：https://www.luogu.com.cn/training/576466#problems

强连通分量

Tarjan 可以用于求强连通分量，然后就可以缩点了。

具体的，我们建出一个 dfs 树，设 $dfn_u$ 为 $u$ 被访问的编号，$low_u$ 表示 $u$ 能连到最靠祖先的 $dfn$。
那么在从 $u$ 搜索 $v$ 时，我们将 $u$ 先入栈，可以知道：
- 如果一个点未被访问，那么 $low_u = low_v$，因为 $v$ 可以到的地方，$u$ 一定可以到。
- 如果一个点已被访问，且在栈中，那么 $low_u=dfn_v$，原因是这时 $v$ 是 $u$ 的祖先。
- 其他情况不用管。

注意到一个强连通分量有且仅有一个点使得 $low_u=dfn_u$，那就是该分量的起始节点，那么这个强连通分量的所有的点在 Tarjan 算法的栈中在 $u$ 之后。

相关题目：B3609 [图论与代数结构 701] 强连通分量。

代码

void dfs(int u) {
    vis[u]=1;
    low[u]=dfn[u]=++dfncnt;
    stk[++stktop]=u;
    for(auto v:G[u]) {
        if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]) {
        anscnt++;
        while(1) {
            int v=stk[stktop--];
            vis[v]=0;
            ans[anscnt].push_back(v);
            if(v==u) break;
        }
        sort(ans[anscnt].begin(),ans[anscnt].end());
    }
}

缩点

我们学会了如何去搜强连通分量，那么把这些强联通分量缩成一个点，就是缩点。
一张有向图，缩点之后会变成一个 DAG。

相关题目：P3387【模板】缩点。

int n,m;
int val[maxn],totval[maxn];
vector<int> G[maxn];
int low[maxn],dfn[maxn],dfncnt;
int stk[maxn],top,anscnt,bel[maxn];
bool vis[maxn];
int a[maxn],b[maxn];
int deg[maxn],dep[maxn],dp[maxn];
void dfs(int u) {
    vis[u]=1;
    dfn[u]=low[u]=++dfncnt;
    stk[++top]=u;
    for(int v:G[u]) {
        if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]) {
        anscnt++;
        while(1) {
            int v=stk[top--];
            vis[v]=0;
            bel[v]=anscnt;
            if(u==v) break;
        }
    }
}
signed main() {
    in2(n,m);
    For(i,1,n) in1(val[i]);
    For(i,1,m) {
        in2(a[i],b[i]);
        G[a[i]].push_back(b[i]);
    }
    For(i,1,n) if(!dfn[i]) dfs(i);
    For(i,1,n) G[i].clear(),totval[bel[i]]+=val[i];
    For(i,1,m) a[i]=bel[a[i]],b[i]=bel[b[i]];
    For(i,1,m) if(a[i]!=b[i]) G[a[i]].push_back(b[i]),deg[b[i]]++;
    queue<int> q;
    For(i,1,n) if(!deg[i]) q.push(i),dp[i]=totval[i];
    int ans=0;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int v:G[u]) {
            dep[v]=dep[u]+1;
            dp[v]=max(dp[v],dp[u]+totval[v]);
            deg[v]--;
            if(!deg[v]) q.push(v);
        }
        ans=max(ans,dp[u]);
    }
    cout<<ans<<'\n';
}