Shared code

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 2e5+5;
vector<int> adj[N];
set<int> adj2[N];
int dfn[N], low[N], scc[N], inst[N], sccid, t, ans[N], val[N], sum[N], dp[N];
vector<pair<int,int>> edges;
stack<int> st;

void dfs(int u){
    dfn[u] = low[u] = ++t;
    st.push(u);
    inst[u] = 1;

    for(auto v : adj[u]){
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u],low[v]);
        }else if(inst[v]){
            low[u] = min(low[u],dfn[v]);
        }
    }

    if(dfn[u]==low[u]){
        sccid++;
        int x;
        do{
            x = st.top();
            st.pop();
            scc[x] = sccid;
            sum[sccid] += val[x];
            inst[x] = 0;
        }while(x!=u);
    }
}


signed main(){
    fastio
    int n,m;
    cin >> n >> m;

    for(int i = 1;i <= n;i++) cin >> val[i];

    for(int i = 0;i < m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        edges.push_back({u,v});
    }

    for(int i = 1;i <= n;i++){
        if(!dfn[i]) dfs(i);
    }

    for(auto [u,v] : edges){
        if(scc[u]!=scc[v]){
            adj2[scc[u]].insert(scc[v]);
        }
    }

    for(int i = sccid;i;i--){
        dp[i] += sum[i];
        for(auto v : adj2[i]){
            dp[v] = max(dp[v],dp[i]);
        }
    }

    cout << *max_element(dp,dp+N) << "\n";
}