USACO 2016 US Open Contest, Gold Problem 2 - Closing the Farm
Problem Link Time Complexity: O(M log N) Algorithm Used: Disjoint Union Set There are N barns, connected by M (1 ≤ N, M ≤ 2 * 10⁵) bidirectional roads. The barns will be closed one by one. Each time a barn is closed, all roads to and from that barn cannot be used. After each barn is closed, find out whether it is possible to reach every open barn from any other open barn. This is a graph problem, since the barns can be represented as nodes and the roads as edges. The graph is unweighted. A naive solution to this problem would be to simulate the situation by closing a barn, then picking an arbitrary open barn and running a DFS to visited all barns possible. If all the barns supposed to be open were not visited (since they are not in the same component), then it is not possible to reach every open barn from any other open barn. This is a simple and straightforward solution that will all produce the correct output, but it would exceed the time limit with a time complexity of O...