链式前向星的代码能发出了对比吗
by Hagasei @ 2023-01-13 22:09:53
@[Stream_X](/user/383785) 这是链式前向星的
```
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=5e5+34,inf=0x3f3f3f3f;
int instack[maxn],dfn[maxn],low[maxn];
int val[maxn];
int tot,col,co[maxn],dp[maxn],w[maxn],MAX;
int v[maxn],u[maxn];
int head[maxn],to[maxn],nex[maxn];
stack<int>stk;
//vector<int>G[maxn];
void addedge(int u,int v){
nex[++tot]=head[u];
head[u]=tot;
to[tot]=v;
}
void Tarjan(int u){
dfn[u]=++tot;
low[u]=dfn[u];
stk.push(u);
instack[u]++;
for(int i=head[u];i;i=nex[i]){
int v=to[i];
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instack[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
co[u]=++col;
val[col]=w[u];
while(stk.top()!=u){
co[stk.top()]=col;
instack[stk.top()]=0;
val[col]+=w[stk.top()];
stk.pop();
}
stk.pop();
instack[u]=0;
}
}
int dfs(int u){
if(dp[u])return dp[u];
int mx=0;
for(int i=head[u];i;i=nex[i]){
int v=to[i];
mx=max(mx,dfs(v));
}
dp[u]=val[u]+mx;
return dp[u];
}
void work(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&u[i],&v[i]);
addedge(u[i],v[i]);
}
tot=0;
for(int i=1;i<=n;i++){
if(!dfn[i])Tarjan(i);
}
// for(int i=1;i<=n;i++)G[i].clear();
memset(head,0,sizeof(head));
memset(nex,0,sizeof(nex));
memset(to,0,sizeof(to));
// for(int i=1;i<=n;i++)val[co[i]]+=w[i];
for(int i=1;i<=m;i++){
if(co[u[i]]==co[v[i]])continue;
addedge(co[u[i]],co[v[i]]);
}
for(int i=1;i<=col;i++)MAX=max(MAX,dfs(i));//dp深搜
printf("%d\n",MAX);
}
int main()
{
work();
return 0;
}
```
by DaShabby @ 2023-01-13 23:03:10
@[DaShabby](/user/672837) ![](https://cdn.luogu.com.cn/upload/image_hosting/tk85yiz6.png)
善用 [diff tool](https://csacademy.com/app/diffing_tool/)
by Hagasei @ 2023-01-14 08:08:29
```
@[Stream_X](/user/383785) 谢谢你,我粗心了
by DaShabby @ 2023-01-14 13:05:00