Застревание с задачей DFS/BFS (серебро USACO)

Question

конкурсное программирование noob здесь. Я пытался решить этот вопрос: http://www.usaco.org/index.php?page=viewproblem2&cpid=646

Код я написал работает только с первым тестом, и дает предел памяти Exceed ошибке - или («!») Для остальных тестов , Это мой код (случайно перепутали M и 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; 
} 

в основном, недействительный ДФСА (интермедиат узел) просматривает двунаправленный граф, начиная от узла до тех пор, пока не достигнет в тупике, и для каждого узла, , [node] станет равным 1. (если посетили -> 1, а не посещено -> 0, выключено -> -1).

bool connected (vector C) возьмет вектор проверки и посмотрит, есть ли какие-либо узлы, которые не были посещены. если эта функция возвращает значение true, это означает, что граф связан, а false - в противном случае.

В основной функции,

1) Я сохранить двунаправленный график, приведенный в задаче в качестве списка смежности.

2) ДФС через него сначала, чтобы видеть, если граф изначально подключен (а затем распечатать «Да» или «НЕТ»), то сброс проверить

3) от 1 до М, я взять значение входного сигнала, который сарай будет закрыт, проверьте [входное значение] = -1 и dfs через него. После этого я сброшу вектор проверки, но сохраняю значения -1, чтобы эти амбары были недоступны для следующих циклов dfs.

Я думаю, что мой алгоритм имеет смысл, но почему это даст MLE и как я могу улучшить свое решение? Я действительно не могу понять, почему мой код дает MLE. Большое спасибо!

Answer 1

1. Ваш ДФС принимает огромную нагрузку стеков и, таким образом, вызывая MLE
2. Попробуйте реализовать его с BFS, который использует очередь. Старайтесь держать очередь глобальной, а не локальной.
3. Ваш подход предоставит вам лимит времени Превышен вердикт. Попытайтесь решить эту проблему более эффективно. Скажем, O (n).