In the problem Closing the Farm (USACO 2016 US Open Silver), my code only runs for the first testcase.
Problem link:
http://www.usaco.org/index.php?page=viewproblem2&cpid=644
USACO Guide link:
My approach was to perform a depth-first search on the graph of the farm to check if it is fully connected for each closed barn. After each DFS, I would then traverse through my visited vector (containing the status of each barn, either visited or not visited). If all the elements in visited are 1 (true), then the current graph is fully connected.
I am now a bit stuck on where the mistake is in my solution/code. Could someone please tell me what I did wrong? Any help would be highly appreciated.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> adj[3001]; //use an adjacency list to store the graph
vector<int> visited; //to keep whether a node is visited or not
vector<int> order; //to keep the order in which the barns will close
//DFS search
void dfs(int s)
{
if(visited[s])
return;
visited[s] = 1;
for(auto u: adj[s])
dfs(u);
}
int main(int argc, char** argv) {
ifstream fin("closing.in");
ofstream fout("closing.out");
int i, j;
int temp1, temp2;
bool b;
fin >> N >> M;
for(i = 0; i < M; i++) {
fin >> temp1 >> temp2;
adj[temp1].push_back(temp2);
adj[temp2].push_back(temp1);
}
for(i = 0; i < N; i++) {
fin >> temp1;
order.push_back(temp1);
}
//check if the graph is fully connected before any closed barns
visited = vector<int>(3001);
dfs(1);
b = false;
for(i = 1; i <= N; i++) {
if(visited[i] != 1) {
b = true;
break;
}
}
if(b)
fout << "NO" << endl;
else
fout << "YES" << endl;
//check if the graph is fully connected for each closed barn
for(i = 0; i < N - 1; i++) {
for(j = 1; j <= N; j++)
visited[j] = 0;
visited[order[i]] = 1;
dfs(order[N-1]);
b = false;
for(j = 1; j <= N; j++)
if(visited[j] != 1) {
b = true;
break;
}
if(b)
fout << "NO" << endl;
else
fout << "YES" << endl;
}
return 0;
}