为什么通过引用 DFS 传递数组会导致内存限制,但全局声明它们会通过所有测试?
错误解决方法:
#include <bits/stdc++.h>
using namespace std;
vector <int> res;
int n, m;
void dfs(int v, vector<vector<int>> graph, vector<int> &used, vector<pair<int, int>> edges)
{
used[v] = 1;
for(int u:graph[v])
{
if(used[u] == 0)
{
for(int j = 1;j <= m;j++)
{
pair<int, int> p1 = {u, v};
pair<int, int> p2 = {v, u};
if(edges[j] == p1 || edges[j] == p2){
res.push_back(j);
break;
}
}
dfs(u, graph, used, edges);
}
}
}
int main()
{
int ind = 1;
cin >> n >> m;
vector <vector<int>> graph(n+1);
vector <int> used(n+1, 0);
vector <pair<int, int>> edges(m+1);
for(int i = 0;i < m;i++)
{
int t1, t2;
cin >> t1 >> t2;
graph[t1].push_back(t2);
graph[t2].push_back(t1);
edges[ind] = {t1, t2};
ind++;
}
dfs(1, graph, used, edges);
cout << res.size() << endl;
for(int x:res) cout << x << " ";
}
恰恰相反:这里是
graph
按值传递:因此,在每个递归步骤中,您都在复制这个二维数组!其实,像这样的:
当您将它们声明为全局时,您根本不需要将它们传递给函数,并且不必每次都复制它们。
尝试通过链接实际传递它们。