/*
易得出状态转移为val[v] = max(val[v],val[pre] + a[v])
于是通过tarjan算法把所有环缩为一点,跑一遍DAG上的DP即可
*/
#include
using namespace std;
const int maxn = 10e5+5;
int scc[maxn],dfn[maxn],low[maxn],stac[maxn];
int a[maxn],head1[maxn],head2[maxn],vis[maxn];
int val[maxn],cnt,cnt1,scc_clock,top,n,m,tot,scc_amount;
struct node{
int to,from,pre;
}g1[maxn*2],g2[maxn*2];//g1为原来的图，g2为缩点后的图
void add1(int from,int to){
g1[++cnt].from = from;
g1[cnt].to = to;
g1[cnt].pre = head1[from];
head1[from] = cnt;
} //对应g1的add操作
void add2(int from,int to){
g2[++cnt1].from = from;
g2[cnt1].to = to;
g2[cnt1].pre = head2[from];
head2[from] = cnt1;
} //对应g2的add操作
void tarjan(int x){
low[x] = dfn[x] = ++scc_clock;//初始化为时间戳
stac[++top] = x;vis[x] = 1;//入栈、标志数组设为1
for(register int i = head1[x];i;i = g1[i].pre){//遍历与x连接的点
int v = g1[i].to;
if(!dfn[v]){
tarjan(v);
low[x] = min(low[x],low[v]);
}else if(vis[v]){
low[x] = min(low[x],dfn[v]);
}
}//一顿tarjan的操作
if(low[x] == dfn[x]){
scc_amount++;
int y;
while(y = stac[top--]){//出栈
scc[y] = x;
vis[y] = 0;//我也不知道为啥
if(x == y) break;
a[x] += a[y];//加权值
}
}
}
int dfs(int u){
val[u] = a[u];
for(int i = head2[u];i;i = g2[i].pre){
int v = g2[i].to;
dfs(v);
val[v] = max(val[v],val[u] + a[v]);
}
}
int main(){
int x,y;
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;i++){
scanf("%d",a+i);
}
for(register int i = 1;i <= m;i++){
scanf("%d%d",&x,&y);
add1(x,y);
}
for(register int i = 1;i <= n;i++){
if(!dfn[i]) tarjan(i);//tarjan算法基本操作
}
for(register int i = 1;i <= m;i++){
x = scc[g1[i].from],y = scc[g1[i].to];
if(x != y){//如果不属于同一强连通分量，就连边
add2(x,y);
}
}
int ans = 0;
for(int i = 1;i <= scc_amount;i++){
if(!val[i]){
dfs(i);
ans = max(ans,val[i]);
}
}
printf("%d\n",ans);
return 0;
}
京公网安备 11010802041100号