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
import java.io.*;
import java.util.*;

public class CoinCollector {
	static ArrayList<Integer>[] graph, revGraph, dag;
	static boolean[] visited;
	static int[] comp;
	static long[] coins, compCoins, dp;
	static ArrayDeque<Integer> stack;