patterncppModerate

Hacker Rank: Journey to the Moon (Graph Theory)

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

therankgraphtheorymoonhackerjourney

Problem

I am attempting to complete the "Journey to the Moon" problem described below:

There are N trained astronauts numbered from 0 to N-1. But those in
charge of the mission did not receive information about the
citizenship of each astronaut. The only information they have is that
some particular pairs of astronauts belong to the same country.

Your task is to compute in how many ways they can pick a pair of
astronauts belonging to different countries. Assume that you are
provided enough pairs to let you identify the groups of astronauts
even though you might not know their country directly. For instance,
if 1,2,3 are astronauts from the same country; it is sufficient to
mention that (1,2) and (2,3) are pairs of astronauts from the same
country without providing information about a third pair (1,3). Print
An integer that denotes the number of permissible ways to choose a
pair of astronauts.

I believe I have implemented a messy solution. I want advice on two fronts:

-
How many a more gracefully implement the DFS algorithm in C++? The current format appears to be very messy and lines like:

for(long i=0; i<ei[ti].size(); ++i){
    ci+= dfs(ei,vi,ei[ti][i]); // try each node in the adjacency list     
}

make my eyes bleed.

-
Why is my current implementation so slow? I have noticed that most other people opted for an adjacency matrix implemented as a single dimensional array as opposed to an adjacency list to store the graph. I suspect that the accesses to the the std::map might be the cause of the issue, but I haven't benchmarked the code to find out. I am curious as to whether there is an optimized map implementation that would better suite the purpose.

-
I also suspect recursion might be the issue. I haven't figured out a way to implement tail recursion in this yet. I did try using "inline" to resolve the issue, but (as expected) it didn't actually help the overall speed.

-
Please feel free to criticize any my C++ style

Solution

The big problem

The reason your program runs so slowly is that your dfs() function takes the edge list as a parameter by value instead of by reference. That means it is making a copy of the edge list on every call (and recursive call). I ran your program against a maximum sized input, but it didn't finish in several minutes (I gave up). But when I changed the edge list argument to a reference, it took only 0.14 seconds.

Cleanup

I realize that this is a programming contest solution, and as such your variable names and comments are a bit messy. But you might want to clean it up at least a little bit before submitting it for code review. At the very least, remove all of the debugging only commented out code.

Initialize vector the simple way

Instead of:

vector v;
for(long i =0; i<n; i++){
    v.push_back(false);   
}//visited initialize false

you could simply write:

vector v(n);

No need for map

I'm not sure why you chose to use a map of vectors for your adjacency list instead of a vector of vectors. It might make sense if you wanted to keep your edge list sparse, but you filled up your map with an empty vector for each vertex. So there is really no benefit to using a map at that point. Once you change the edge list to a vector of vectors, you could simplify its initialization to this:

vector> edges(n);

Sample rewrite

Here is how I would have rewritten your program with all of the above in mind:

#include 
#include 
using namespace std;

// Count Nodes with DFS
long long dfs(vector> &edges, vector  &visited,
        long long vertex)
{
    // If it's visited bail
    if (visited[vertex] == true)
        return 0;

    visited[vertex] = true;
    long long count = 1;
    for (size_t i=0; i > numVertices >> numEdges;

    vector visited(numVertices);
    vector> edges(numVertices);

    //Build adjacency matrix
    while (numEdges--) {
        long long from, to;
        cin >> from >> to;
        edges[from].push_back(to);
        edges[to  ].push_back(from);
    }

    long long sum         = 0;
    long long alreadySeen = 0;
    for (long i=0; i<numVertices; ++i) {
        if (!visited[i]) {
            long long count = dfs(edges, visited, i);
            sum = sum + (alreadySeen * count);
            alreadySeen += count;
        }
    }
    cout << sum << "\n";

    return 0;
}

Bonus code: union find implementation

As mentioned in the comments, I thought that this problem would be better solved with a union find algorithm. I wrote a sample solution, and you can compare it with the depth first search solution:

#include 
#include 

static inline int Count(const std::vector &groups, int head)
{
    return -groups[head];
}

static int Find(std::vector &groups, int node)
{
    if (groups[node]  &groups, int a, int b)
{
    int parentA = Find(groups, a);
    int parentB = Find(groups, b);

    if (parentA == parentB)
        return;

    int countA   = Count(groups, parentA);
    int countB   = Count(groups, parentB);
    int newCount = countA + countB;

    if (countA > countB) {
        groups[parentB] = parentA;
        groups[parentA] = -newCount;
    } else {
        groups[parentA] = parentB;
        groups[parentB] = -newCount;
    }
}

int main(void)
{
    int n, p;

    std::cin >> n >> p;

    std::vector groups(n, -1);

    for (int i = 0; i > a >> b;
        Union(groups, a, b);
    }

    long long total     = 0;
    long long prevCount = 0;
    for (int i = 0; i < n; i++) {
        if (Find(groups, i) == i) {
            int count = Count(groups, i);

            total     += count * prevCount;
            prevCount += count;
        }
    }
    std::cout << total << "\n";
}

Code Snippets

vector<bool> v;
for(long i =0; i<n; i++){
    v.push_back(false);   
}//visited initialize false

vector<bool> v(n);

vector<vector <long long>> edges(n);

#include <vector>
#include <iostream>
using namespace std;

// Count Nodes with DFS
long long dfs(vector<vector<long long>> &edges, vector <bool> &visited,
        long long vertex)
{
    // If it's visited bail
    if (visited[vertex] == true)
        return 0;

    visited[vertex] = true;
    long long count = 1;
    for (size_t i=0; i < edges[vertex].size(); ++i) {
        // try each node in the adjacency list
        count += dfs(edges, visited, edges[vertex][i]);
    }
    return count;
}

int main()
{
    long long numVertices, numEdges;
    cin >> numVertices >> numEdges;

    vector<bool> visited(numVertices);
    vector<vector <long long>> edges(numVertices);

    //Build adjacency matrix
    while (numEdges--) {
        long long from, to;
        cin >> from >> to;
        edges[from].push_back(to);
        edges[to  ].push_back(from);
    }

    long long sum         = 0;
    long long alreadySeen = 0;
    for (long i=0; i<numVertices; ++i) {
        if (!visited[i]) {
            long long count = dfs(edges, visited, i);
            sum = sum + (alreadySeen * count);
            alreadySeen += count;
        }
    }
    cout << sum << "\n";

    return 0;
}

#include <iostream>
#include <vector>

static inline int Count(const std::vector<int> &groups, int head)
{
    return -groups[head];
}

static int Find(std::vector<int> &groups, int node)
{
    if (groups[node] < 0)
        return node;
    return (groups[node] = Find(groups, groups[node]));
}

static void Union(std::vector<int> &groups, int a, int b)
{
    int parentA = Find(groups, a);
    int parentB = Find(groups, b);

    if (parentA == parentB)
        return;

    int countA   = Count(groups, parentA);
    int countB   = Count(groups, parentB);
    int newCount = countA + countB;

    if (countA > countB) {
        groups[parentB] = parentA;
        groups[parentA] = -newCount;
    } else {
        groups[parentA] = parentB;
        groups[parentB] = -newCount;
    }
}

int main(void)
{
    int n, p;

    std::cin >> n >> p;

    std::vector<int> groups(n, -1);

    for (int i = 0; i < p; i++) {
        int a, b;
        std::cin >> a >> b;
        Union(groups, a, b);
    }

    long long total     = 0;
    long long prevCount = 0;
    for (int i = 0; i < n; i++) {
        if (Find(groups, i) == i) {
            int count = Count(groups, i);

            total     += count * prevCount;
            prevCount += count;
        }
    }
    std::cout << total << "\n";
}

Context

StackExchange Code Review Q#157193, answer score: 12

Revisions (0)

No revisions yet.