Journey to the moon Problem(graphs)

help
, ,
1

I am trying a problem on hacker rank where I am getting the TLE for some cases for following code. So i assumed that may output is coming late but when I run the code in my local compiler using the same test cases,I am getting run time error(i.e. No output at all)
I tried running the debugger but still can’t figure out what is wrong with the code.

#include <bits/stdc++.h>

using namespace std;
 
/*
 * Complete the 'journeyToMoon' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. 2D_INTEGER_ARRAY astronaut
 */
  
}

void dfs(int n, vector<vector<int>> adj, vector<int> &visited, int src,int &count)
{

    visited[src] = 1;
    count++;
   
    for (auto it : adj[src])
    {
        if (!visited[it])
        {
            dfs(n, adj, visited, it,count);
        }
    }
}

int journeyToMoon(int n,vector<vector<int>> adj)
{


    // vector<vector<int>> adj(n);
    // createAdjacencyList(n, astronaut, adj);

    vector<int> visited(n, 0);

    vector<int> components;
    int count=0;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
           dfs(n, adj, visited, i,count);
            components.push_back(count);
            count=0;
        }
    }

    
   
     int totalPairs=(n*(n-1))/2;
     int value;
     int check;
     for(int i=0;i<components.size();i++)
     {
          check=components[i];
         value=((components[i])*(components[i]-1))/2;
             totalPairs-=value;
         
         
     }
     
     return totalPairs;

}

int main()
{
    int n,p;
    cin>>n>>p;
    vector<vector<int>> adj(n);
    for(int i=0;i<p;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int result = journeyToMoon(n,adj);

    cout << result << "\n";

    // fout.close();

    return 0;
}

Problem Link:-

2

Pass adj by reference (like you’ve done with vector<int> &visited), not by value.

3

Do We have to pass by reference even when we are not making changes to it?
If yes,why?

4

You don’t have to, but it’s much more efficient than passing by value, which makes a copy of adj every single time and will almost certainly TLE.

5

Thanks,
now it is passing for all test cases.
IT was failing for 1 test case even after applying your suggestion but passed it when I changed the data type to long long int.

1 Like