2016 US Open Problem 3, Closing The Farm

Problem Info

Link: USACO

My Work

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

vector<int> ne[3000];//array of vectors, neighbor list
bool s[3000];//'seen' array, lets us record which barns we have visited.
int f;//visited barn count

void dfs(int b, int t) {//depth first search algorithm, input b is the barn we are at and input t is the number of open barns
	s[b] = true;//we've now visited barn b, so we set s[b] to true
	f++;//add 1 to the visited barn count
	int i;
	if (f != t) {//if we haven't visited all open barns
		for (i = 0; i < ne[b].size(); i++) {//cycle through neighbors of barn b
			if (s[ne[b][i]] != true) {//if we haven't visited it
				dfs(ne[b][i], t);//run dfs on it
			}
		}
	}
}

int main() {
	ifstream fin("closing.in");
	ofstream fout("closing.out");
	int M;
	int N;
	fin >> N;
	fin >> M;
	int r[3000];
	int a;
	int l;
	int z;
	for (a = 0; a < M; a++) {
		fin >> l;//input the roads
		fin >> z;
		l--;//0 index it
		z--;
		ne[l].push_back(z);//add z to list of neighbors of l
		ne[z].push_back(l);//add l to list of neighbors of z
	}
	int b;
	for (b = 0; b < N; b++) {
		fin >> r[b];//input the barns order of removal
		r[b] = r[b] - 1;//0 index it
	}
	int i;
	int j;
	int k;
	for (j = 0; j < N; j++) {
		s[j] = false;//set seen to false
	}
	f = 0;//set f to 0
	dfs(r[N - 1], N);//run the first dfs (we use r[N - 1] because it is the last barn, therefore we don't have an issue where we start with a removed barn)
	if (f == N) {//if we visited all N barns
		fout << "YES" << '\n';//the farm is connected, so we output "YES"
	}
	else {
		fout << "NO" << '\n';//otherwise the farm is not connected, so we output "NO"
	}
	for (i = 1; i < N; i++) {//for i barns removed
		for (j = 0; j < N; j++) {//for each barn
			for (k = 0; k < ne[j].size(); k++) {//cycles through neighbors
				if (ne[j][k] == r[i - 1]) {//if the neighbor is to be removed
					ne[j].erase(ne[j].begin() + k);//remove it from the list, in this way we can eliminate a barn from the network.
				}
			}
		}
		for (j = 0; j < N; j++) {
			s[j] = false;//set seen to false
		}
		f = 0;//set f to 0
		dfs(r[N - 1], N - i);//run dfs
		if (f == N - i) {//if we visited all N - i open barns
			fout << "YES" << '\n';//output "YES"
		}
		else {
			fout << "NO" << '\n';//otherwise output "NO"
		}
	}
}
If we run a DFS on any barn and visit all the other open barns, then the farm is connected. Therefore, my program simulates the removal of the barns, and runs a DFS on the barn that is not removed at each point in time.

## What I have Tried
I have tried downloading the test data and putting it into my code in a C++ shell. The test cases I got wrong were 2, 3, and 6. When I put case 2's test data into the shell, the first disparity was when the barn removed was barn N. I don't know if that's relevant, and I don't see what's wrong with my code.
Please help debug.

Sorry for the formatting problems, I haven’t posted in a while.

Please read the section regarding finding a small test case that your program fails on.

That’s no excuse for not properly formatting your post :neutral_face: