如标题,自己造的几个数据都过了,查代码查不到什么问题 求助dalao
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e5+10;
vector<int>G[N],rG[N],scc[N];
// 正图 反图 连通分量图
vector<int>S;//存储第一次dfs结果,标记点的先后顺序
int vis[N],sccid[N],numscc;
// 节点所在scc序号
int a[N],u[N],v[N],w[N];
//
int ans=-1,dp[N];
void dfs1(int u){
if(vis[u])return;
vis[u]=1;
for(int i=0;i<G[u].size();i++)dfs1(G[u][i]);
S.push_back(u);//最后再压入自己
}
void dfs2(int u){
if(sccid[u])return;
sccid[u]=numscc;
w[numscc]+=a[u];
for(int i=0;i<rG[u].size();i++)dfs2(rG[u][i]);
}
void kosaraju(int n){
numscc=0;S.clear();
memset(sccid,0,sizeof(sccid));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)dfs1(i);
for(int i=n-1;i>=0;i--){
if(!sccid[S[i]]){
numscc++; dfs2(S[i]);//有限递归栈顶元素
}
}
}
void dfs3(int u){
if(dp[u])return;
for(int i=0;i<scc[u].size();i++){
if(dp[scc[u][i]])continue;
dfs3(scc[u][i]);
dp[u]=max(dp[u],dp[scc[u][i]]);
}
dp[u]+=w[u];
}
int main(){
//freopen("P3387_1.in","r",stdin);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
cin>>u[i]>>v[i];
G[u[i]].push_back(v[i]);
rG[v[i]].push_back(u[i]);
}
kosaraju(n);
for(int i=1;i<=m;i++){
if(sccid[u[i]]!=sccid[v[i]]){
scc[sccid[u[i]]].push_back(sccid[v[i]]);
}
}
for(int i=1;i<=numscc;i++){
if(dp[i])continue;
dfs3(i);
ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}