tarjan缩点

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7;
int h[N],e[N],ne[N],idx;
int stk[N],instk[N],low[N],dfn[N];
int id[N],cnt,tim,top,s[N],w[N];
int xx[N],yy[N],dp[N];
void tarjan(int u)
{
	stk[++top]=u;
	dfn[u]=low[u]=++tim;
	instk[u]=1;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(dfn[v]==0)
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(instk[v]==1)
		{
			low[u]=min(dfn[v],low[u]);
		}
		if(dfn[u]==low[u])
		{
        	cnt++;
        	while(stk[top+1]!=u)
			{
            	id[stk[top]]=cnt;
            	s[cnt]+=w[stk[top]];
            	instk[stk[top--]]=0;
        	}
    	}
	}
}
void add(int u,int v)
{
	e[idx]=v;
	ne[idx]=h[u];
	h[u]=idx++;
}
int n,m;
void dfs(int x)
{
	if(dp[x]!=0)
	return ;
	dp[x]=s[x];
	int ans=0;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(dp[j]==0)dfs(j);
		ans=max(ans,dp[j]);
	}
	dp[x]+=ans;
}
int main()
{
	memset(h,-1,sizeof(h));
	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",&xx[i],&yy[i]);
		add(xx[i],yy[i]);
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
		tarjan(i);
	}
	memset(h,-1,sizeof(h));
	memset(ne,-1,sizeof(ne));
	memset(e,0,sizeof(e));
	idx=0;
	for(int i=1;i<=m;i++)
	{
		if(id[xx[i]]!=id[yy[i]])
		{
			add(id[xx[i]],id[yy[i]]);
		}
	}
	int mx=-1;
	for(int i=1;i<=cnt;i++)
	{
		if(dp[i]==0)
		{
			dfs(i);
		}
	}
	for(int i=1;i<=cnt;i++)
	mx=max(mx,dp[i]);
	printf("%d",mx);
	return 0;
}
re+wa 50分
QWQ