#3#4#5#7 WA

P3387【模板】缩点

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,i,j,u,v,cnt,cntb,ans,maxn;
int a[N],dfn[N],low[N],sum[N],fei[N],sz[N],ru[N],jin[N],cun[N];
int sd[N],h[N];
bool ins[N];
stack<int>s;
vector<int>ed[N];
vector<int>ned[N];
vector<int>belong[N];
void tarjin(int u){
	cnt++;dfn[u]=low[u]=cnt;ins[u]=1;s.push(u);
	for(int i=0;i<ed[u].size();i++)
	{
		int v=ed[u][i];
		if(!dfn[v]){
			tarjin(v);low[u]=min(low[u],low[v]);
		}
		else if(ins[v])
		low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		cntb++;int node;
		do{
			node=s.top();s.pop();ins[node]=0;
			belong[cntb].push_back(node);
		}while(node!=u);
	}
}
void dfs(int u)
{
	jin[u]=1;ans+=sum[u];
	for(int it:ned[u])
	{
		if(!jin[it])dfs(it);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=m;i++)
	{
		cin>>u>>v;
		ed[u].push_back(v);
	}
	for(i=1;i<=n;i++)
		if(!dfn[i])
			tarjin(i);
	for(i=1;i<=cntb;i++)
	{
		for(j=0;j<belong[i].size();j++)
		{
			sum[i]+=a[belong[i][j]];
			cun[belong[i][j]]=i;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<ed[i].size();j++)
		{
			if(cun[i]!=cun[ed[i][j]])
				ned[cun[i]].push_back(cun[ed[i][j]]);
		}
	}
	
	for(i=1;i<=cntb;i++)
	{
		for(j=0;j<ned[i].size();j++)
		{
			ru[ned[i][j]]++;
		}
	}
	for(i=1;i<=cntb;i++)
	{
		if(ru[i]==0)
		{
			ans=0;
			dfs(i);
			maxn=max(ans,maxn);
		}
	}
	cout<<maxn;
	return 0;
}