# 【題解】CSES 1686 Coin Collector

【解題想法】SCC + 拓撲排序

```#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";
}
```