USACO 2016 US Open #3 (Silver): Closing the Farm

Farmer John and his cows are planning to leave town for a long vacation, and so FJ wants to temporarily close down his farm to save money in the meantime.

The farm consists of N barns connected with M bidirectional paths between some pairs of barns (1≤N, M≤3000). To shut the farm down, FJ plans to close one barn at a time. When a barn closes, all paths adjacent to that barn also close, and can no longer be used.

FJ is interested in knowing at each point in time (initially, and after each closing) whether his farm is “fully connected” — meaning that it is possible to travel from any open barn to any other open barn along an appropriate series of paths. Since FJ’s farm is initially in somewhat in a state of disrepair, it may not even start out fully connected.

INPUT FORMAT (file closing.in):

The first line of input contains N and M. The next M lines each describe a path in terms of the pair of barns it connects (barns are conveniently numbered 1…N). The final N lines give a permutation of 1…N describing the order in which the barns will be closed.

OUTPUT FORMAT (file closing.out):

The output consists of NN lines, each containing “YES” or “NO”. The first line indicates whether the initial farm is fully connected, and line i+1 indicates whether the farm is fully connected after the i th closing.

SAMPLE INPUT:

4 3
1 2
2 3
3 4
3
4
1
2

SAMPLE OUTPUT:

YES
NO
YES
YES

Basically what I thought at first was DFS; since I only have to check up to 3000 points and see if they are all connected.

The issue when the farm is closed; it would be way too time-costly if you were to actually ‘erase’ the points as you go. Therefore, you have to use another method.

What I used in this case was I marked in an array (since there are only up to 3000 points) if the points were closed or not, and I just DFSed the way through. The whole time complexity would be O(MN), but since they both are 3000 at max, it would be 3e6, which is enough for the silver problem.

However, I do think I can shorten the time by going backwards; by starting with only one point, then building up the roads and see if the connection effects the farm.

Well, here’s my code anyways:

//
//  main.cpp
//  Closing the Farm (silver)
//
//  Created by Shin Lee on 26/03/2020.
//  Copyright © 2020 Shin Lee. All rights reserved.
//

#include <bits/stdc++.h>
using namespace std;
int n, m;
set<int>s;
vector<int>connect[3005];
int order[3005]; int closed[3005]; int visit[3005];
void dfs(int pos){
    if(visit[pos]!=0 or closed[pos]==1)return;
    s.insert(pos);
    visit[pos]=1;
    for(int i=0;i<connect[pos].size();i++){
        dfs(connect[pos][i]);
    }
}
int main(){
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        connect[a].push_back(b);
        connect[b].push_back(a);
    }
    for(int i=0;i<n;i++)cin >> order[i];
    
    dfs(1);
    if(s.size()==n)printf("YES\n");
    else printf("NO\n");
    for(int i=0;i<n-1;i++){
        s.clear();
        memset(visit,0,sizeof(visit));
        closed[order[i]]=1;
        dfs(order[n-1]);
        if(s.size()==n-i-1){
            printf("YES\n");
        }else printf("NO\n");
        
    }
    
    return 0;
    
}

Sorry if the code looks stupid; I can’t afford wordpress premium 😦