WA #1 #3 #4 #5 #7 #9

#include<bits/stdc++.h>
#define	MAX_N 10005
#define MAX_M 100005 
using namespace std;
int n,m,a[MAX_N],u,v,ans;
int head[MAX_N],to[MAX_M],Next[MAX_M],tot,hc[MAX_N],toc[MAX_M],nc[MAX_M],tc;
int dfn[MAX_N],low[MAX_N],Stack[MAX_N],top,num,cnt,c[MAX_N],b[MAX_N];
bool ins[MAX_N];
int in[MAX_N],t[MAX_N],sum;
queue<int> q;
int f[MAX_N];
void add_edge(int x,int y){
	to[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
}
void addc(int x,int y){
	toc[++tc]=y;
	nc[tc]=hc[x];
	hc[x]=tc;
}
void tarjan(int x){
	dfn[x]=low[x]=++num;
	Stack[++top]=x;	ins[x]=1;
	for(int i=head[x];i;i=Next[i]){
		if(!dfn[to[i]]){
			tarjan(to[i]);
			low[x]=min(low[x],low[to[i]]);
		}
		else	low[x]=min(low[x],dfn[to[i]]);
	}
	if(low[x]==dfn[x]){
		cnt++;
		do{
			int y=Stack[top--];
			b[cnt]+=a[y];
			c[y]=cnt;
			ins[y]=0;
		}while(ins[x]);
	}
}
void topsort(){
	for(int i=1;i<=cnt;i++)
		if(!in[i]){
			q.push(i);
			f[i]=b[i];//顺便初始化 
			ans=max(ans,f[i]);
		}
	while(q.size()){
		int tt=q.front();
		t[++sum]=tt;	q.pop();
		for(int i=hc[tt];i;i=nc[i]){
			in[toc[i]]--;
			if(!in[toc[i]])	q.push(toc[i]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		add_edge(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])	tarjan(i);
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=Next[j]){
			if(c[i]==c[to[i]])	continue;
			addc(c[i],c[to[i]]);
		}
	for(int i=1;i<=cnt;i++)
		for(int j=hc[i];j;j=nc[j])
			in[toc[j]]++;
	topsort();
	for(int i=1;i<=sum;i++)
		for(int j=hc[i];j;j=nc[j]){
			f[toc[j]]=max(f[toc[j]],f[i]+b[toc[j]]);
			ans=max(ans,f[toc[j]]);
		}
	printf("%d",ans);
	return 0;
}