WA on #4 #7

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>

using namespace std;

const int MAXN=1e4+5, MAXM=1e5+5;
int n, m, a[MAXN];

int timer, vis[MAXN];
int dfn[MAXN], low[MAXN];
vector <int> G[MAXN], H[MAXN];
struct Stack {
	int top, num[MAXN];
}stk;
int id[MAXN];
struct Edge {
	int u, v;
}e[MAXM];

void Tarjan (int u, int fa) {
	low[u]=dfn[u]=++timer;
	vis[u]=true;
	stk.num[++stk.top]=u;
	
	for (int v:G[u]) {
		if (v==fa) continue;
		if (dfn[v]) {
			low[u]=min (low[u], dfn[v]);
			continue;
		}
		Tarjan (v, u);
		low[u]=min (low[v], low[u]);
	}
	if (low[u]==dfn[u]) {
		while (true) {
			if (u!=stk.num[stk.top])
				a[u]+=a[stk.num[stk.top]];
			id[stk.num[stk.top]]=u;
			if (stk.num[stk.top]==u) {
				stk.top--;
				break;
			}
			stk.top--;
		}
	}
}

int f[MAXN];
int F (int u) {
	if (vis[u]) return f[u];
	vis[u]=true;
	for (int v:H[u])
		f[u]=max (F(v), f[u]);
	f[u]+=a[u];
	return f[u];
}

int ans;

int main () {
	freopen("P3387.in", "r", stdin);
	freopen("P3387.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
	for (int i=1; i<=n; i++) id[i]=i;
	for (int i=1; i<=m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[i]=(Edge){u, v};
		G[u].push_back(v);
	}
	
	for (int i=1; i<=n; i++)
		if (!vis[i]) Tarjan (i, 0);
	
	
	for (int i=1; i<=m; i++) {
		e[i].u=id[e[i].u], e[i].v=id[e[i].v];
		if (e[i].u==e[i].v) continue;
		H[e[i].u].push_back(e[i].v);
	}
	
	memset (vis, 0, sizeof vis);
	for (int i=1; i<=n; i++)
		if (!vis[i]&&id[i]==i) ans=max (ans, F(i));
	
	printf("%d\n", ans);
	return 0;
}