USACO Bronze 2019 December - Milk Factory

Official Analysis

This problem can also be solved using Depth-First Search (a Silver topic). Represent the factory as a directed unweighted graph with edges from $b_i$ to $a_i$ for all $i$. For every node $i\in [1,N]$, we start a DFS at node $i$ and check whether this results in every other node being visited. We can keep track of whether the current DFS visits all nodes with a boolean array whose entries are initially set to false. If every node is visited, then we print $i$. Otherwise, if there exists no $i$ such that this condition is satisfied, then we print $-1$.

Implementation

import java.io.*;
import java.util.*;

class Graph{
	 private int V;
	 private ArrayList<ArrayList<Integer>> adj;
	 Graph(int V){
		 this.V = V;
		 adj = new ArrayList<ArrayList<Integer>>(V);
		 for(int i = 0; i < V; i++){

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using str = string;
using bb = bool;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vb = vector<bb>;
using vs = vector<str>;