# Memory limit exceeded ? what to do?

#1

`
#include <bits/stdc++.h>

int dfs(int source, int parent, vector & visited, map <int,list> l)
{
visited[source] = 1;

``````for (auto nbr : l[source])
{

if (visited[nbr] == 0)
{int ans =  dfs(nbr,source,visited,l);
if (ans)
{
return 1;
}
}
else
{
if (nbr != parent)
{

return 1;
}

}
}

return 0;
``````

}

int Solution::solve(int A, vector<vector > &B) {

``````vector <int> visited (A + 1, 0);
map <int,list<int>> l;

for (int i = 0 ; i < B.size() ; i ++)
{
l[B[i][0]].push_back(B[i][1]);
l[B[i][1]].push_back(B[i][0]);

}

for (int i = 1  ; i < visited.size() ; i ++)
{
if (visited[i] == 0)
{
if ( dfs(i,-1,visited,l))
return 1;
}
}

return 0;
``````

}
`

#2

I also got a MLE doing similar implementation, were you able to find out the reason for this?
My Code:

``````#include<bits/stdc++.h>

bool isCyclic(int src, int parent, unordered_map<int, list<int>> &g, unordered_map<int, bool> &visited){
visited[src]=true;
for(auto neighbour: g[src]){
if(!visited[neighbour]){
if(isCyclic(neighbour, src, g, visited)) return true;
}
else if(neighbour!=parent) return true;
}
return false;
}

int Solution::solve(int A, vector<vector<int> > &B){
unordered_map<int, list<int>> g;
for(int i=0; i<B.size(); i++){
g[B[i][0]].push_back(B[i][1]);
g[B[i][1]].push_back(B[i][0]);
}
unordered_map<int, bool> visited;
for(int i=1; i<=A; i++){
if(!visited[i]){
if(isCyclic(i, -1, g, visited)) return 1;
}
}
return 0;
}``````

#3

check for infinite recursion

#4

I dont understnad. My solution is correct and has the same space complexity as the one provided. But my solution is exceeding memory limit. What wrong with this website???

#5

try passing by reference

#6

Create global variables and change the size for each testcase

#7

Try using union find method. For using DFS, you need to create an adjacency list and visited array which takes up more memory than a union find method which only uses a parent array. so space complexity is significantly reduced