Stuck with DFS/BFS task (USACO silver)

Question

competitive programming noob here. I've been trying to solve this question: http://www.usaco.org/index.php?page=viewproblem2&cpid=646

The code I wrote only works with the first test case, and gives a Memory Limit Exceed error -- or ('!') for the rest of the test cases. This is my code (accidently mixed up M and N):

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
using std::vector;
vector<int> check;
vector< vector<int> > A;
void dfs(int node)
{
    check[node] = 1;
    int siz = A[node].size();
    for (int i = 0; i < siz; i++)
    {
        int y = A[node][i];
        if (check[y] == 0)
        {
            dfs(y);
        }
    }
}

bool connected(vector<int> C)
{
    for (int i = 1; i <= C.size() - 1; i++)
    {
        if (C[i] == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    freopen("closing.in", "r", stdin);
    freopen("closing.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    int M, N;
    cin >> M >> N;
    check.resize(M + 1);
    A.resize(M + 1);
    for (int i = 0; i < N; i++)
    {
        int u, v;
        cin >> u >> v;
        A[u].push_back(v); A[v].push_back(u);
    }
    dfs(1);
    if (!connected(check)) {
        cout << "NO" << "\n";
    }
    else {
        cout << "YES" << "\n";
    }
    fill(check.begin(), check.end(), 0);
    for (int j = 1; j < M; j++)
    {
        int node;
        bool con = true;
        cin >> node;
        check[node] = -1;
        for (int x = 1; x <= N; x++)
        {
            if (check[x] == 0)
            {
                dfs(x);
                break;
            }
        }
        if (!connected(check)) {
            cout << "NO" << "\n";
        }
        else {
            cout << "YES" << "\n";
        }
        for (int g = 1; g <= M; g++)
        {
            if (check[g] == 1)
            {
                check[g] = 0;
            }
        }
    }
    return 0;
}

basically, void dfs(int node) searches through the bidirectional graph starting from node until it reaches a dead end, and for each node that is visited, check[node] will become 1. (if visited -> 1, not visited -> 0, turned off -> -1).

bool connected(vector C) will take the check vector and see if there are any nodes that weren't visited. if this function returns true, it means that the graph is connected, and false if otherwise.

In the main function,

1) I save the bidirectional graph given in the task as an Adjacency list.

2) dfs through it first to see if the graph is initially connected (then print "Yes" or "NO") then reset check

3) from 1 to M, I take the input value of which barn would be closed, check[the input value] = -1, and dfs through it. After that, I reset the check vector, but keeping the -1 values so that those barns would be unavailable for the next loops of dfs.

I guess my algorithm makes sense, but why would this give an MLE, and how could I improve my solution? I really can't figure out why my code is giving MLEs. Thanks so much!

Answer 1

1. Your DFS is taking huge load of stacks and thus causing MLE
2. Try to implement it with BFS which uses queue. Try to keep the queue as global rather than local.
3. Your approach will give you Time Limit Exceeded verdict. Try to solve it more efficiently. Say O(n).