algorithm - 坚持 DFS/BFS 任务(USACO 银牌)

Question

竞争性编程菜鸟在这里。我一直在尝试解决这个问题: http://www.usaco.org/index.php?page=viewproblem2&cpid=646

我编写的代码仅适用于第一个测试用例，并为其余测试用例提供超出内存限制错误或 ('!')。这是我的代码(不小心混淆了 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;
}

基本上，void dfs(int node) 从node开始遍历双向图，直到到达死胡同，每访问到一个node，check[node]就会变为1。(如果访问过 -> 1，未访问过 -> 0，关闭 -> -1)。

bool connected(vector C) 将获取检查向量并查看是否有任何未访问的节点。如果此函数返回 true，则表示图是连通的，否则返回 false。

在主函数中，

1) 我将任务中给出的双向图保存为邻接表。

2) 先dfs遍历看图是否初始连通(然后打印“Yes”或“NO”)然后重置检查

3) 从 1 到 M，我取将要关闭的谷仓的输入值，检查[输入值] = -1，并通过它进行 dfs。之后，我重置了检查向量，但保留了 -1 值，以便这些谷仓在 dfs 的下一个循环中不可用。

我想我的算法是有道理的，但为什么这会给出 MLE，我该如何改进我的解决方案？我真的不明白为什么我的代码会提供 MLE。非常感谢!

Answer 1

1. 你的 DFS 正在承受巨大的堆栈负载，从而导致 MLE
2. 尝试用使用队列的 BFS 来实现它。尝试将队列保持为全局队列而不是本地队列。
3. 你的方法会给你超过时间限制的判决。尝试更有效地解决它。说 O(n)。