CSES - Coin Collector

Time Complexity: $\mathcal O(N+M)$

First, we split the graph into SCCs. We then treat each component as a node. So then, If the coin collector enters a component, he can collect all the coins in it.

Since the resulting graph is a DAG, we can use DP to find the maximum coins that can be collected.

Copy
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define rsz resize

#define F0R(i, a) for (int i = 0; i < (a); i++)