卡住DFS/BFS任務（USACO銀）

這裏有競爭力的編程noob。我一直在試圖解決這個問題： http://www.usaco.org/index.php?page=viewproblem2&cpid=646 卡住DFS/BFS任務（USACO銀）

我寫的代碼只與第一個測試用例一起工作，並給出了超出內存限制的錯誤 - 或（'！'）用於其餘的測試用例。這是我的代碼（意外地混合起來，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; 
}

基本上，空隙DFS（INT節點）搜索通過雙向圖形從節點開始，直到它到達一個死端，並且對於每個節點那訪問時，檢查[節點]將變爲1. （如果訪問 - > 1，未訪問 - > 0，關閉 - > -1）。

布爾連接（向量C）將採取檢查向量，並查看是否有任何未訪問的節點。如果此函數返回true，則表示圖形已連接，否則爲false。

在主函數，

1）I保存在任務作爲一個鄰接表中給出的雙向圖表。

2）DFS通過它首先以查看是否圖表最初被連接（然後打印「是」或「否」），則重置檢查

3）從1至M，I採取其輸入值穀倉將被關閉，檢查[輸入值] = -1，並通過它的dfs。之後，我重置檢查向量，但保留-1值，以便這些穀倉將不可用於dfs的下一個循環。

我想我的算法是有道理的，但爲什麼這會給一個MLE，我該如何改進我的解決方案？我真的不知道爲什麼我的代碼給MLEs。非常感謝！

來源

2017-01-22 user7455168

問題可能出在DFS的遞歸實現上。每次調用都會將至少sizeof（siz）+ sizeof（y）+ sizeof（void（*）（））'字節添加到調用堆棧中，並且調用堆棧的大小相當有限（通常爲1 -8 Mb）。在最壞的情況下，它會進行200000次遞歸調用並導致堆棧溢出。 – Anton

如果你通過C參考連接，它會有幫助嗎？ –

啊！這就是它給出MLE錯誤的原因。非常感謝你的幫助！ – user7455168

你DFS正在堆棧的巨大的負荷而發生MLE
嘗試使用BFS它使用隊列實現它。儘量保持隊列爲全局而不是本地。
你的方法會給你超出時限的判決。嘗試更有效地解決它。說O（n）。

來源

2017-01-23 16:16:47 faisal47

嘿，非常感謝你的建議！我使用BFS方法重寫了我的代碼，並且它可以工作（10/10測試用例）。但這是否意味着對於這些問題，我應該使用BFS方法而不是DFS來避免MLE（除非問題只能通過DFS方法解決）？ – user7455168

有些問題顯然需要DFS。像自下而上的DP'一樣。 DFS是理解非常重要的概念。但是無論你看到哪裏都可以逃離，那麼你應該去BFS。 – faisal47

卡住DFS/BFS任務（USACO銀）

回答

相關問題