【題解】CSES 1686 Coin Collector

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
 
int n, m, a, b, dfn[100005], stk[100005], low[100005], pa[100005], in[100005], k[100005], scc, idx;
long long coins[100005], dp[100005], ans;
vector <int> v[200005];
vector <int> v2[200005];
stack <int> st;
 
void tarjan(int x){
    idx++;
    dfn[x] = low[x] = idx;
    st.push(x);
    stk[x] = 1;
    for (auto i:v[x]){
        if (!dfn[i]){
            tarjan(i);
            low[x] = min(low[x], low[i]);
        }
        else if (stk[i]){
            low[x] = min(low[x], dfn[i]);
        }
    }
    if (dfn[x] == low[x]){
        scc++;
        pa[x] = scc;
        int nxt = -1;
        while (nxt != x){
            nxt = st.top();
            st.pop();
            pa[nxt] = scc;
            stk[nxt] = 0;
        }
    }
}
void build(){
    for (int i = 1; i <= n; i++){
        coins[pa[i]] += k[i];
        for (int j:v[i]){
            if (pa[i] != pa[j]){
                v2[pa[i]].push_back(pa[j]);
                in[pa[j]]++;
            }
        }
    }
}
void topo(){
    queue <int> q;
    for (int i = 1; i <= scc; i++){
        if (in[i] == 0) q.push(i);
    }
    while (!q.empty()){
        int now = q.front();
        q.pop();
        dp[now] += coins[now];
        ans = max(ans, dp[now]);
        for (auto i:v2[now]){
            in[i]--;
            dp[i] = max(dp[i], dp[now]);
            if (!in[i]) q.push(i);
        }
    }
}
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> k[i];
    }
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        v[a].push_back(b);
    }
    for (int i = 1; i <= n; i++){
        if (!dfn[i]) tarjan(i);
    }
    build();
    topo();
    cout << ans << "\n";
}