直接给他缩点然后求新的图的完整版：
C2[u]表示缩点后的u点这个环上的点实际上是哪些
G3[u]表示缩点后的u点的出边还是一样，要记得先处理入链。（可以让这个图好看一点但是没啥鸟用）入链可能会有一些特别的性质，当然假如入链没有特别性质也可以直接缩点。
不对其实直接缩点就可以了，入链还是新图的入链，环是他自己，题目给的环内性质就直接搬过来就可以了。
所以可以直接Kosaraju。
这里就是缩点之后出度为0的点的数量只有1的话，就是那个出度为0的点代表的环。
下面这个有点bug，重边没插进来，但是却计算了出度。
#include要记得新图里加入的u是缩点后的u，v也是！using namespace std;typedef long long ll;const int MAXN = 105;const int INF = 0x3f3f3f3f;int n, w[MAXN], indeg[MAXN];vector G[MAXN], G2[MAXN];//从i点出发的连通分量，染色为c1[i]int c1[MAXN], cntc1;//i点所在的强连通分量，染色为c2[i]int c2[MAXN], cntc2;//第i个强连通分量内的点vector C2[MAXN];int s[MAXN], cnts;void dfs1(int u) { c1[u] = cntc1; for (int v : G[u]) if (!c1[v]) dfs1(v); s[++cnts] = u;}void dfs2(int u) { C2[cntc2].push_back(u); c2[u] = cntc2; for (int v : G2[u]) if (!c2[v]) dfs2(v);}void Kosaraju() { //再计算环 for (int i = 1; i <= n; ++i) if (!c1[i]) { ++cntc1; dfs1(i); } for (int i = n; i >= 1; --i) if (!c2[s[i]]) { ++cntc2; dfs2(s[i]); }}set G3[MAXN];int outdeg3[MAXN];int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku int m; scanf("%d%d", &n,&m); for(int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G2[v].push_back(u); ++indeg[v]; } for (int i = 1; i <= n; ++i) if (!c1[i] && indeg[i] == 0) { ++cntc1; dfs1(i); } Kosaraju(); for(int u = 1; u <= cntc2; ++u) { for(auto ui : C2[u]) { for(auto vi : G[ui]) { if(c2[vi] != u) { G3[u].insert(c2[vi]); ++outdeg3[u]; } } } } int out0 = 0, sum = 0; for(int u = 1; u <= cntc2; ++u) { if(outdeg3[u] == 0) { ++out0; sum += C2[u].size(); } } printf("%d\n", (out0 == 1) ? sum : 0); return 0;}
#includeusing namespace std;typedef long long ll;const int MAXN = 10005;const int INF = 0x3f3f3f3f;int n, w[MAXN];vector G[MAXN], G2[MAXN];//从i点出发的连通分量，染色为c1[i]int c1[MAXN], cntc1;//i点所在的强连通分量，染色为c2[i]int c2[MAXN], cntc2;int DP[MAXN];//第i个强连通分量内的点vector C2[MAXN];int s[MAXN], cnts;void dfs1(int u) { c1[u] = cntc1; for (int v : G[u]) if (!c1[v]) dfs1(v); s[++cnts] = u;}void dfs2(int u) { C2[cntc2].push_back(u); DP[cntc2] += w[u]; c2[u] = cntc2; for (int v : G2[u]) if (!c2[v]) dfs2(v);}void Kosaraju() { //再计算环 for (int i = 1; i <= n; ++i) if (!c1[i]) { ++cntc1; dfs1(i); } for (int i = n; i >= 1; --i) if (!c2[s[i]]) { ++cntc2; dfs2(s[i]); }}set GT3[MAXN], G3[MAXN];int outdeg3[MAXN];int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku int m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) { scanf("%d", &w[i]); } for(int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G2[v].push_back(u); } Kosaraju(); /*for(int i = 1; i <= n; ++i) { printf("i=%d c2=%d\n", i, c2[i]); }*/ for(int u = 1; u <= cntc2; ++u) { for(auto ui : C2[u]) { for(auto vi : G[ui]) { if(c2[vi] != u && !G3[u].count(c2[vi])) { ++outdeg3[u]; G3[u].insert(c2[vi]); GT3[c2[vi]].insert(u); } } } } queue Q; for(int i = 1; i <= cntc2; ++i) if(outdeg3[i] == 0) Q.push(i); int ans = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); for(auto v : GT3[u]) { outdeg3[v]--; if(outdeg3[v] == 0) Q.push(v); } int maxv = 0; for(auto v : G3[u]) maxv = max(maxv, DP[v]); DP[u] += maxv; ans = max(ans, DP[u]); } printf("%d\n", ans); return 0;}