tarjan算法可以用来求强连通块的块数，判断条件是low[x] = dfn[x]； 注意点：缩点后是将强连通块当作点，所以重建图的时候，发现原图2点不在同一强连通块就可以按照原图的方向链接2个超级点。 建图可以能有重边但是大部分不会对解题产生影响。如果有需要可以用set去重。
tarjan 当 low[x] = dfn[x] 时，弹出 x 包括x前面的元素，这些元素共同组成一个量连通块。不要忘记标记他们已经被弹出了
vis[stack[top--]] = 0; // 弹出P3387 【模板】缩点
#include<cstring> #include<queue> #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<set> #include<cmath> #include<string> #define ll long long #define max(a,b) a > b ? a : b #define min(a,b) a < b ? a : b #define me(a,b) memset(a, b, sizeof(a)) #define iosos ios::sync_with_stdio(false) #define fo(a,b,c) for(int a = b; a < c; a++) using namespace std; const int maxn = 1e5 + 10; const int maxm = maxn << 1; const int inf = 0x7f7f7f7f; int h[maxn], h1[maxn], p, p1; int point[maxn], w[maxn], color[maxn], sum; int n, m; int dfn[maxn], low[maxn], cnt; int stack[maxn], top; int vis[maxn]; int deg[maxn]; int dp[maxn]; struct edge { int nes,u, to; }e[maxm], e1[maxm]; inline void add(int u, int v) { e[p].nes = h[u], e[p].to = v, e[p].u = u, h[u] = p++; } inline void add1(int u, int v) { e1[p1].nes = h1[u], e1[p1].to = v, h1[u] = p1++; } void tarjan(int x) { dfn[x] = low[x] = ++cnt; vis[x] = 1; stack[++top] = x; for(int i = h[x]; ~i; i= e[i].nes) { int v = e[i].to; if(!dfn[v]){ tarjan(v); low[x] = min(low[x], low[v]); } else if(vis[v]) { low[x] = min(low[x], low[v]); } } if(dfn[x] == low[x]) { ++sum; while(stack[top+1] != x) { color[stack[top]] = sum; //标记块 w[sum] += point[stack[top]]; //合并块 vis[stack[top--]] = 0; // 弹出 } } } int main() { iosos; me(h,-1); me(h1, -1); cin>>n>>m; fo(i,1,n+1) cin>>point[i]; fo(i, 0, m) { int u, v; cin>>u>>v; add(u, v); } fo(i,1,n+1) if(!dfn[i]) tarjan(i); fo(i, 0, p) { //枚举所有边 int u = e[i].u, v = e[i].to; if(color[u] != color[v]) { // 如果原图上的2点不在同一超级点 则链接他们所在的超级点 add1(color[u], color[v]); //重新建图 deg[color[v]]++; //超级点入读加1 } } queue<int > q; fo(i,1,sum+1) dp[i] = w[i]; for(int i = 1; i <= sum; i++) { //讲入读为0的超级点加入 if(!deg[i]) { q.push(i); } } while(!q.empty()) { //边top边dp 无后效 int u = q.front(); q.pop(); for(int i = h1[u]; ~i; i = e1[i].nes) { int v = e1[i].to; dp[v] = max(dp[v], w[v] + dp[u]); --deg[v]; if(deg[v] == 0) q.push(v); } } int ans = 0; fo(i,1,sum+1) ans = max(ans, dp[i]); cout<<ans; return 0; }