Hacker Rank: Journey to the Moon (Graph Theory)

Question

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:

1. 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.

2. 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.

3. 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.

4. Please feel free to criticize any my C++ style in this, I'm fairly rusty.

5. I fully expect someone to point out some condition where the thing loops forever rather than exiting. If that's the case I am still am interested in hearing people's outlook on 1, 2, and 3.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map> 
using namespace std;
map <long long,vector <long long>> e; //edges 

//Count Nodes with DFS
long dfs(map <long long,vector<long long>> ei, vector <bool> &vi,long long ti){ //graph, visited, target
    //if it's visited bail
    //cout << "entering dfs with target " << ti << endl; 
    if(vi[ti] == true){
        //cout << "revisit of " << ti << " prevented" << endl << endl;
        return 0;
    }else{
        //cout << "vi[ti] of " << ti << " was false!" << endl;
    }  

    vi[ti] = true; 
    long long ci =1; 
    for(long i=0; i<ei[ti].size(); ++i){
        ci+= dfs(ei,vi,ei[ti][i]); // try each node in the adjacency list     
    }
    //cout << "going to return ci of " << ci << endl;
    return ci; 
    //Deal with singletons
} 

int main() {
    long long n,p,q,z; 
    cin >> n >> p; 
    vector<bool> v;
    for(long i =0; i<n; i++){
        v.push_back(false);   
    }//visited initialize false

    //Initialize all them vectors. 
    for(long i =0; i<n; ++i){
        vector <long long> tv;
        e.insert(pair <long long, vector<long long>>(i,tv)); 
    }
    //cout << "survived init" << endl;
    //Build adjacency matrix 

    while(p--){
        cin >> q >> z;
        e[q].push_back(z); //should work 
        e[z].push_back(q);
    }

    //cout << "survived adj matrix" << endl; 

    long long sum = 0; 
    long long as = 0; 
    for(long i =0; i<n; ++i){
        //cout << "Trying " << i << " now" << endl; 
        if(v[i] == false){
            //cout << "v[" << i << "]" << " should now be true" << endl; 
            long long t=0; 
            //Only go this far if we have not visited. 
            t = dfs(e,v,i); //sum = sum + (total nodes so far) * current node
            //cout << "sum = " << " " << sum << " + (" << as << " * " << t << ")" << endl; 
            //Multiply
            sum = sum + (as * t);
            as += t; 
        }else{
            //cout << "i of " << i << " was false" << endl; 
        } 
    }
    //Profit
    cout << sum; 

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    return 0;
}

Answer 1

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<bool> v;
for(long i =0; i<n; i++){
    v.push_back(false);   
}//visited initialize false

you could simply write:

vector<bool> 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<vector <long long>> edges(n);

Sample rewrite

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

#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;
}

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 <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";
}