是这样：
你的tarjan缩点是正确的，而重新建图部分你需要向新图添加所有原图的边。
即将
```cpp
for (int i = 1; i <= n; ++i){
int xx = fa[a[i]], yy = fa[b[i]];
if (xx != yy) {
G[xx].push_back(yy);
++in[yy];
}
}
```
改为
```cpp
for (int i = 1; i <= m; ++i){
int xx = fa[a[i]], yy = fa[b[i]];
if (xx != yy) {
G[xx].push_back(yy);
++in[yy];
}
}
```
然后你在topo sort中找到入度为零的点，就将它加入队列中了。没有验证它是否是这个强连通分量的“根节点”(即最早探索到的节点)，这导致一个强连通分量的节点多次入队，造成错误。
这个错误的改法很多，这里只说一种：将所有强连通分量中的节点染成“根节点”的编号，并在入队时特判
by ENJOuYang @ 2024-01-21 12:06:51
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int NR = 1e4 + 5;
int n,m,dis[N],a[N],b[N],in[NR],fa[NR],dfn[NR],low[NR],dp[NR],cnt,sum,ans = -1;
vector<int> g[NR];
vector<int> G[NR];
bool vis[NR];
stack<int> st;
void Tarjan (int x){
st.push(x);
vis[x] = 1;
++cnt;
dfn[x] = cnt;
low[x] = cnt;
for (int i = 0; i < g[x].size(); ++i){
int nxt = g[x][i];
if (dfn[nxt] == 0){
Tarjan(nxt);
low[x] = min (low[x], low[nxt]);
}else if (vis[nxt] == 1){
low[x] = min (low[x], low[nxt]);
}
}
if (dfn[x] == low[x]){
while (st.top() != x && !st.empty()){
//cout<<st.top()<<" ";
int tmp = st.top(); st.pop();
fa[tmp] = x;
vis[tmp] = 0;
dis[x] += dis[tmp];
}
fa[x]=x;
//cout<<st.top()<<endl;
vis[x] = 0;
st.pop();
}
return ;
}
void topo (){
queue<int> q;
for (int i = 1; i <= n; ++i){
if (fa[i]==i && in[i] == 0){
q.push(i);
dp[i] = dis[i];
}
}
while (!q.empty()){
int tmp = q.front();
q.pop();
for (int i = 0; i < G[tmp].size(); ++i){
int nxt = G[tmp][i];
dp[nxt] = max (dp[nxt], dp[tmp] + dis[nxt]);
--in[nxt];
if (in[nxt] == 0) q.push(nxt);
}
}
return ;
}
signed main (){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> dis[i];
for (int i = 1; i <= m; ++i){
cin >> a[i] >> b[i];
g[a[i]].push_back(b[i]);
}
for (int i = 1; i <= n; ++i){
if (dfn[i] == 0) Tarjan(i);
}
for (int i = 1; i <= m; ++i){
int xx = fa[a[i]], yy = fa[b[i]];
if (xx != yy) {
G[xx].push_back(yy);
++in[yy];
}
}
//for (int i = 1; i <= n; ++i)cout<<fa[i]<<" ";
//puts("");
topo();
for (int i = 1; i <= n; ++i) ans = max (ans, dp[i]);
cout << ans << '\n';
return 0;
}
```
by ENJOuYang @ 2024-01-21 12:11:47
@[HuYangMu2011](/user/632311) 不是有必要写 topo 吗，我 $n^2$ dfs 过了。
by Super_Builder @ 2024-01-21 13:50:34
@[HuYangMu2011](/user/632311) $n^2$ 建图不香吗，非要多开两个数组建图。
最后附上 AC 代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define scd second
#define N 10005
int cnt=0,n,m,ww[N],dfn[N],low[N],vis[N],w[N],idx=0,scc[N];
vector<int>e[N],e2[N];
stack<int>stk;
void tarjan(int u){
vis[u]=1;
dfn[u]=low[u]=++cnt;
stk.push(u);
for(auto v:e[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(dfn[v],low[u]);
}
}
if(dfn[u]==low[u]){
idx++;
while(stk.top()!=u){
vis[stk.top()]=0;
scc[stk.top()]=idx;
stk.pop();
}
vis[stk.top()]=0;
scc[stk.top()]=idx;
stk.pop();
}
}
int dfs(int u){
int maxx=0;
for(auto v:e2[u]){
maxx=max(maxx,dfs(v));
}
return maxx+w[u];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>ww[i];
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=n;i++){
w[scc[i]]+=ww[i];
}
for(int i=1;i<=n;i++){
for(auto v:e[i]){
if(scc[i]!=scc[v])
e2[scc[i]].push_back(scc[v]);
}
}
int ans=0;
// cout<<idx<<endl;
for(int i=1;i<=idx;i++){
ans=max(ans,dfs(i));
}
cout<<ans;
return 0;
}
```
by Super_Builder @ 2024-01-21 13:53:11
%%%%%@[Xu_dh](/user/820227)
by huyangmu @ 2024-01-22 08:03:13
已关%%%@[ouyang09](/user/798144)
by huyangmu @ 2024-01-22 09:16:22