Time Complexity: O(N+M)\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.

C++

#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++)

Java

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;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum