С++ DFS, Memory limit
Почему передача массивов по ссылке в DFS вызывает Memory Limit, а их объявление глобально проходит все тесты?
Решение с ошибкой:
#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 << " ";
}
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
Скорее наоборот: здесь у вас передача graph
по значению:
void dfs(int v, vector<vector<int>> graph
так что на каждом шаге рекурсии вы копируете этот двумерный массив! Собственно, как и этот:
void dfs( ... vector<pair<int, int>> edges
При объявлении их как глобальных вы не передаете их в функции вовсе, и копировать каждый раз их не приходится.
Попробуйте реально передавать их по ссылке.