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(N²). Instead of running DFS for every barn closed, we use another way to quickly check the number of barns in a component. 

If we close barns in the order they are closed, then we wouldn't be able to know if all barns, except for the one being closed, are in the same component or not without running a DFS. So, we iterate over the barns being closed, from the last barn closed to the first barn closed, and add them to the graph, essentially "opening" the barns up. When the last barn closed is "opened", basically added to the graph, it is the only barn open so the graph is fully connected.

From there, we proceed by opening barns in the reverse order they were closed. Every time barn i is opened, the number of components of the graph increases by 1, since barn i is initially not connected to any other barn in the graph. Then, we iterate over the barns that barn i is connected to and check if barn j has been opened yet. If it hasn't then barn j isn't in the graph, so we can ignore it. Otherwise, barn j is in the graph and we need to connect it to all components possible. Every time barn j connects to a component, the total number of components in the graph decreases by 1. The barn connectivity can be represented using a disjoint union set. 

After connecting barn i to every possible component, check the total number of components. If there is more than 1 component, then the open barns are not reachable from each other and the answer is NO. Otherwise, they are all connected and the answer is YES.

Since we found the answers in the reverse order of barns closed, print the answers in the reverse order found.

Code

#include <bits/stdc++.h>

using namespace std;

vector <vector <int>> adj;

vector <int> links, comp_size;

int no_of_comps;

int find(int x){

    while (x != links[x])

        x = links[x];

    return x;

}

bool same(int a, int b){

    return find(a) == find(b);

}

void unite(int a, int b){

    a = find(a);

    b = find(b);

    /*

       only connect the two nodes if they are not part

       of the same component

    */

    if (!same(a, b)){

        if (comp_size[a] < comp_size[b])

            swap(a, b);

        comp_size[a] += comp_size[b];

        links[b] = a;

        no_of_comps--;

    }

}

int main()

{

    freopen("closing.in", "r", stdin);

    freopen("closing.out", "w", stdout);

    int n, m;

    cin >> n >> m;

    adj.resize(n+1);

    for (int i = 0; i < m; i++){

        int a, b;

        cin >> a >> b;

        adj[a].push_back(b);

        adj[b].push_back(a);

    }

    vector <int> removals(n);

    vector <bool> opened(n+1, false);

    for (int i = 0; i < n; i++)

        cin >> removals[i];

    links.resize(n+1);

    for (int i = 1; i <= n; i++)

        links[i] = i;

    comp_size.resize(n+1, 1);

    vector <bool> ans(n);

    for (int i = n-1; i >= 0; i--){

        int a = removals[i];

        no_of_comps++;

        opened[a] = true;

        for (auto b : adj[a]){

            if (!opened[b])

                continue;

            unite(a, b);

        }

        if (no_of_comps > 1)

            ans[i] = false;

        else

            ans[i] = true;

    }

    for (auto i : ans){

        if (i)

            cout << "YES\n";

        else

            cout << "NO\n";

    }

    return 0;

}