C++竞赛编程：依赖用户输入大小的数组无法全局化，DFS传参求助

方案1：改用std::vector替代变长数组（推荐） #

C++标准并不支持变长数组（VLA）（比如vector<int> mygraph[n+1]这种写法是部分编译器的扩展特性，并非标准语法），改用标准容器vector是最稳妥的解决方案：

• 把邻接表改成vector<vector<int>>类型，访问标记改成vector<bool>类型，两者都可以通过引用传递给递归函数，完全满足DFS的需求（无需拷贝，能修改原数据）。

示例代码：

#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, vector<vector<int>>& mygraph, vector<bool>& visited) {
    visited[u] = true;
    // 处理当前节点的逻辑（比如输出节点）
    cout << u << " ";
    // 遍历邻接节点
    for (int v : mygraph[u]) {
        if (!visited[v]) {
            dfs(v, mygraph, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 初始化邻接表和访问标记
    vector<vector<int>> mygraph(n + 1);
    vector<bool> visited(n + 1, false);
    
    // 读入边构建图
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        mygraph[a].push_back(b);
        mygraph[b].push_back(a);
    }
    
    // 从节点1开始DFS
    dfs(1, mygraph, visited);
    return 0;
}

方案2：用指针传递变长数组（不推荐） #

如果你坚持使用变长数组（仅适用于支持该扩展的编译器，比如GCC），可以通过指针传递：

• 数组名会自动退化为指针，递归函数接收vector<int>*和bool*类型的参数，就能访问原数组的数据。

示例代码：

#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, vector<int>* mygraph, bool* visited) {
    visited[u] = true;
    cout << u << " ";
    for (int v : mygraph[u]) {
        if (!visited[v]) {
            dfs(v, mygraph, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> mygraph[n + 1];
    bool visited[n + 1] = {false}; // 部分编译器支持变长数组初始化
    
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        mygraph[a].push_back(b);
        mygraph[b].push_back(a);
    }
    
    dfs(1, mygraph, visited);
    return 0;
}

注意：这种写法不具备跨编译器的可移植性，竞赛中如果遇到严格遵循C++标准的编译器会报错，因此不推荐。

方案3：动态分配数组（不推荐） #

可以用new手动分配数组，但需要自己管理内存（用完后用delete释放），竞赛场景下容易因疏忽导致内存泄漏，不如vector方便，这里仅作参考：

#include <iostream>
#include <vector>
using namespace std;

void dfs(int u, vector<int>** mygraph, bool* visited, int n) {
    visited[u] = true;
    cout << u << " ";
    for (int v : mygraph[u]) {
        if (!visited[v]) {
            dfs(v, mygraph, visited, n);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    // 动态分配邻接表数组
    vector<int>** mygraph = new vector<int>*[n + 1];
    for (int i = 0; i <= n; ++i) {
        mygraph[i] = new vector<int>();
    }
    // 动态分配访问标记数组
    bool* visited = new bool[n + 1](); // ()初始化所有元素为false
    
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        mygraph[a]->push_back(b);
        mygraph[b]->push_back(a);
    }
    
    dfs(1, mygraph, visited, n);
    
    // 手动释放内存
    for (int i = 0; i <= n; ++i) {
        delete mygraph[i];
    }
    delete[] mygraph;
    delete[] visited;
    return 0;
}

内容的提问来源于stack exchange，提问作者Jēkabs