```
#include <bits/stdc++.h>
#define size si
using namespace std ;
const int N = 114514, M = 5e5 + 10 ;
int n, m;
int e[M], ne[M], h[N], hs[N], idx ;
int dfs[N], low[N] ;
bool st[N] ;
stack <int> stk ;
int ti, scc_cnt ;
int id[N], size[N] ;
int f[N], a[N] ;
void add(int h[], int a, int b) {
e[idx] = b ;
ne[idx] = h[a] ;
h[a] = idx ++ ;
}
void tarjan(int u) {
dfs[u] = low[u] = ++ ti ;
stk.push(u), st[u] = 1 ;
for (int i = h[u] ; i != -1; i = ne[i]) {
int j = e[i] ;
if (!dfs[j]) {
tarjan(j) ;
low[u] = min(low[u], low[j]) ;
} else if (st[j])
low[u] = min(low[u], dfs[j]) ;
}
if (low[u] == dfs[u]) {
int y ;
++ scc_cnt ;
do {
y = stk.top() ;
stk.pop() ;
st[y] = 0 ;
size[scc_cnt] += a[y] ;
id[y] = scc_cnt ;
} while (y != u) ;
}
}
int d[N] ;
int search(int u) {
if (hs[u] == -1 )
return size[u] ;
if (d[u])
return d[u] ;
int ans = 0 ;
for (int i = hs[u]; i != -1; i = ne[i]) {
int j = e[i] ;
ans = max(ans, search(j) + size[u]) ;
}
d[u] = ans ;
return d[u] ;
}
int main() {
cin >> n >> m ;
memset(h, -1, sizeof h) ;
memset(hs, -1, sizeof hs) ;
for (int i = 1 ; i <= n ; i ++)
cin >> a[i] ;
while (m --) {
int a, b ;
cin >> a >> b ;
add(h, a, b) ;
}
for (int i = 1; i <= n ; i ++)
if (!dfs[i])
tarjan(i) ;
for (int i = 1 ; i <= n ; i ++) {
for (int j = h[i]; j != -1 ; j = ne[j]) {
int k = e[j] ;
int a = id[i], b = id[k] ;
if (a != b) {
add(hs, a, b) ;
}
}
}
int ans = 0 ;
for (int i = scc_cnt ; i ; i --) {
if (!f[i])
f[i] = size[i], ans = max(ans, f[i]) ;
for (int j = hs[i] ; j != -1 ; j = ne[j]) {
int k = e[j] ;
f[k] = max(f[k], f[i] + size[k]) ;
ans = max(ans, f[k]) ;
}
}
cout << ans ;
return 0 ;
}
//终于改成了，没取max
//这里给大家贴一个不用拓扑的代码（肯定不是我不会拓扑）
```
by DreamTsinghua @ 2023-10-28 08:44:15
%%%
by hh20080501hh @ 2024-01-10 20:30:16