Official Analysis (C++)

In this problem, we are asked to determine if all remaining barns are connected as the barns close one at a time. To check this, we can run a depth-first search (DFS) starting from the barn that will close last. To simulate the closure of each barn, we can store a boolean array and set each barn in the iteration to be "closed". Then, we can run the DFS and check how many nodes have been visited. If all the unclosed nodes have been visited, then we print "YES" otherwise, we print "NO".

Implementation

Time Complexity: $\mathcal{O}(N^2 + NM)$

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

public class closing {
	// Store global variables used by dfs
	static ArrayList<ArrayList<Integer>> adj;
	static boolean[] visited, closed;
	static int nodes;

	public static void main(String[] args) throws IOException {