Tarjan算法求SCC，缩点

• Tanjan算法可以在O(n + m)的时间内求出强连通分量，常数小，是个非常优秀的算法。
• 算法实现过程：
  dfn[x]表示x的dfs生成树上的编号，代表着时间戳，low[x]表示从x结点出发，能够访问到最早的时间戳。
  <1>进入u时，盖上时间戳，结点入栈。
  <2>枚举该点的结点的时候，分为三种情况：
  （1）如果该点v没有访问过，那么就对v进行深搜，然后返回的时候更新low[u]，
  因为u是v的父节点，v能到达的点，u肯定能够到达，所以能够更新；
  （2）若v已经访问过了，但是v点还是在栈中，那么说明v点是u的祖先结点或者是左子树的兄弟结点，也就是返祖边或者是横叉边，那么就用dfn[v]来更新low[u]。
  （3）若v已经访问过并且已经不在栈中，说明v已经搜索完毕了，那么就直接忽略就可以了。
  <3>离开u点时，记录SCC，只有遍历完所有的SCC时才可以出栈，更新low的意义就是防止有点提前出栈。所以只有当low[u] == dfn[u]的时候才可以更新当前连通分量。

点击查看代码

#include<bits/stdc++.h>                      
using namespace std;
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
//#define int long long
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vvi vector<vector<int>>
typedef long long ll;
typedef tuple<int,int,int> tp;
typedef pair<int,int> PII;
typedef pair<ll,pair<ll,ll>> PIII;
typedef pair<ll,pair<ll,pair<ll,ll>>> pIIII;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
struct SCC {
    int n,cnt,idx;
    vi stk,instk;
    vi dfn,low,scc,siz;
    vvi g;
    SCC() {};
    SCC(int _n) {init(_n);}
    void init(int _n) {
        this -> n = _n;
        g.assign(_n + 1,vi());
        instk.resize(_n + 1);
        dfn.resize(_n + 1);
        low.resize(_n + 1);
        scc.resize(_n + 1);
        siz.resize(_n + 1);
        idx = cnt = 0;
    }
    void add(int u,int v) {
        g[u].emplace_back(v);
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++idx;
        stk.emplace_back(u),instk[u] = 1;
        for(auto v : g[u]) {
            if(!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u],low[v]);
            } else if(instk[v]) {
                low[u] = min(low[u],dfn[v]);
            }
        }

        if(dfn[u] == low[u]) {
            int y;++cnt;
            do {
                y = stk.back();instk[y] = 0;
                scc[y] = cnt;
                stk.pop_back();
                siz[cnt]++;
            } while(y != u);
        }
    }
    void work() {
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) tarjan(i);
        }
    }
};
void solve() {
}
signed main() {	
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
    //system("pause");
	return 0;
}
/*
Do smth instead of nothing and stay organized
Don't get stuck on one approach
*/

• 缩点：其实缩点就是把一个有向有环图变成DAG图，这样就可以做很多DAG图上的操作。缩点的逻辑就是把一个强连通分量算作是一个点，那么整张图里面就不存在环了。
• 缩点的过程：
  <1>因为SCC是按dfs序更新的，所以1号点所在的SCC是最后一个强连通分量。所以我们就从第一个点开始枚举每个点所有的邻点，如果这个值所在的SCC和枚举的点所在的SCC不同，那么就说明这个点是两个SCC的交点，然后就直接连一条边就行了，因为我们的SCC都是已经编过号了，所以直接连边就可以了。重复了也没关系，如果有强迫症的话可以unique一下，没什么影响，因为交点的数量不会很多。

点击查看代码

#include<bits/stdc++.h>                      
using namespace std;
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vpi vector<pair<int,int>>
typedef long long ll;
typedef tuple<int,int,int> tp;
typedef pair<long long,long long> PII;
typedef pair<ll,pair<ll,ll>> PIII;
typedef pair<ll,pair<ll,pair<ll,ll>>> pIIII;
const int N = 2e5 + 7;
const ll inf = 1e18;
const int mod = 998244353;
struct SCC {
    int n,cnt,idx;
    vi stk,instk;
    vi dfn,low,scc,siz;
    vvi g;
    SCC() {};
    SCC(int _n) {init(_n);}
    void init(int _n) {
        this -> n = _n;
        g.assign(_n + 1,vi());
        instk.resize(_n + 1);
        dfn.resize(_n + 1);
        low.resize(_n + 1);
        scc.resize(_n + 1);
        siz.resize(_n + 1);
        idx = cnt = 0;
    }
    void add(int u,int v) {
        g[u].emplace_back(v);
    }
    void tarjan(int u) {
        dfn[u] = low[u] = ++idx;
        stk.emplace_back(u),instk[u] = 1;
        for(auto v : g[u]) {
            if(!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u],low[v]);
            } else if(instk[v]) {
                low[u] = min(low[u],dfn[v]);
            }
        }

        if(dfn[u] == low[u]) {
            int y;++cnt;
            do {
                y = stk.back();instk[y] = 0;
                scc[y] = cnt;
                stk.pop_back();
                siz[cnt]++;
            } while(y != u);
        }
    }
    void work() {
        for(int i = 1; i <= n; i++) {
            if(!dfn[i]) tarjan(i);
        }
    }
};
void solve() {
    int n,m;cin >> n >> m;
    vi dp(n + 1),w(n + 1),nw(n + 1);
    vvi ng(n + 1,vi());
    SCC g(n);
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= m; i++) {
        int u,v;cin >> u >> v;
        g.add(u,v);
    }
    g.work();
    for(int i = 1; i <= n; i++) {
        nw[g.scc[i]] += w[i];
        for(auto v : g.g[i]) {
            int a = g.scc[i],b = g.scc[v];
            if(a != b) {
                ng[a].push_back(b);
            }
        }
    }
    for(int i = g.cnt; i >= 1; i--) {
        if(dp[i] == 0) dp[i] = nw[i];
        for(auto v : ng[i]) {
            dp[v] = max(dp[v],dp[i] + nw[v]);
        }
    }
    int ans = -1e9;
    for(int i = 1; i <= g.cnt; i++) {
        ans = max(ans,dp[i]);
    }
    cout << ans << "\n";
}
signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
    //system("pause");
	return 0;
}
/*
Do smth instead of nothing and stay organized
Don't get stuck on one approach
*/