USACO 2016 US Open Contest Silver Division - Field Reduction

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Given the small constraints, we can simply check whether the graph is connected or not after every single step, without worrying about the complexity. Therefore, this is a simple DFS exercise.

Source code

The source code in C++ can be seen below.

#include <fstream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

bool isConnected(const vector<vector<int>>& graph, const vector<bool>& open, int n) {
    int start = -1, openCount = 0;
    for (int i = 1; i <= n; i++) {
        if (open[i]) {
            openCount++;
            if (start == -1) {
                start = i;
            }
        }
    }
    if (openCount == 0) {
        return 0;
    }

    vector<bool> visited(n + 1, 0);
    queue<int> q;
    q.push(start);
    visited[start] = 1;
    int count = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        count++;
        for (int nb : graph[cur]) {
            if (open[nb] && !visited[nb]) {
                visited[nb] = 1;
                q.push(nb);
            }
        }
    }
    return (count == openCount);
}

int main() {
    ifstream cin("closing.in");
    ofstream cout("closing.out");

    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> order(n);
    for (int i = 0; i < n; i++) {
        cin >> order[i];
    }

    vector<bool> open(n + 1, true);
    if (isConnected(graph, open, n)) {
        cout << "YES\n";
    }
    else {
        cout << "NO\n";
    }
    for (int i = 0; i < n - 1; i++) {
        open[order[i]] = false;
        if (isConnected(graph, open, n)) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
    return 0;
}