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