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.