# HackerRank Journey to the Moon problem solution

In this HackerRank Journey to the Moon problem solution, The member states of the UN are planning to send 2 people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ids. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.

## Problem solution in Python.

```import sys

def findPrt(a):
if prt[a] < 0:
return a
prt[a] = findPrt(prt[a])
return prt[a]

def join(a, b):
a = findPrt(a)
b = findPrt(b)
if a != b:
prt[a] = b

n, i = int(n), int(i)
prt = [-1 for k in range(n)]
for k in range(i):
a, b = int(a), int(b)
join(a, b)

count = [0 for k in range(n)]
for k in range(n):
pk = findPrt(k)
count[pk] = count[pk] + 1
print(sum([a * (n - a) for a in count]) // 2)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {
int[] group = new int[n];
long[] count = new long[n+1];
group[0] = 1; count[1] = 1;
int curGroup = 1;
int unassignedNode = 1;
while (!q.isEmpty()){
int cur = q.removeFirst();
if (group[next]==0){
group[next] = curGroup;
count[curGroup]++;
}
if (q.isEmpty()){
while(unassignedNode<n && group[unassignedNode]!=0) unassignedNode++;
if (unassignedNode<n){
curGroup++;
group[unassignedNode] = curGroup;
count[curGroup]++;
unassignedNode++;
}
}
}
long result = 0;
long total = 0;
for (int i=0; i<=curGroup; i++)
total += count[i];
for (int i=0; i<=curGroup; i++){
total -= count[i];
result += total*count[i];
}
System.out.print(result);
}

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for (int i=0; i<n; i++)
for (int i=0; i<m; i++){
int x = sc.nextInt();
int y = sc.nextInt();
}
}
}```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

bool visited[100001] = {0};

struct node {
vector<long long> neighbour;
};

long long bfs(long long, node *);

int main() {
long long n,m;
scanf("%lld %lld", &n, &m);
node nodelist[n];
long long a,b;
while(m--) {
scanf("%lld %lld", &a, &b);
nodelist[a].neighbour.push_back(b);
nodelist[b].neighbour.push_back(a);
}

long long connected = 0; //no of connected components
long long total = 0;
long long temp = 0;
std::vector<int> count;
for (long long i = 0; i < n; ++i) {
if(!visited[i]) {
temp = bfs(i, nodelist);
count.push_back( temp );
total += temp;
connected++;
}
}
long long answer = (total * (total - 1)) / 2;
for (int i = 0; i < connected; ++i) {
answer -= (count[i] * (count[i] - 1)) / 2;
}

}

long long bfs(long long nod, node *nodelist) {
int count = 0;
queue<long long> Q;
Q.push(nod);
long long n;
while(!Q.empty()) {
n = Q.front();
Q.pop();
if(visited[n]) {
continue;
}
visited[n] = true;
count++;
for (vector<long long>::iterator itr = nodelist[n].neighbour.begin(); itr != nodelist[n].neighbour.end(); ++itr) {
if(!visited[*itr]) {
Q.push(*itr);
}
}
}
return count;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>

// search for root of p.
long long int Find(long long int *uf, long long int p)
{
while (p != uf[p])
p = uf[p];
return p;
}

// Use Union to link p and q to root of tree.
void Union(long long int *uf, int *sz, long long int p, long long int q, int *count)
{
long long int pRoot = Find(uf, p);
long long int qRoot = Find(uf, q);

if (pRoot == qRoot)
return;

if (sz[pRoot] < sz[qRoot]) {
uf[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else {
uf[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
(*count)--;
}

int main()
{
int n, l;
scanf("%d%d", &n, &l);
if (n == 1)
{
printf("0\n");
return(0);
}
long long int **pairs = (long long int**)malloc(sizeof(int*)*l);
for (int i = 0; i < l; i++) {
pairs[i] = (long long int*)calloc(2, sizeof(long long int));
scanf("%lld %lld", &pairs[i][0], &pairs[i][1]);
}

long long int ans = 0;

/** Write code to compute answer using n,l,pairs**/

long long int *uf = (long long int *)malloc(n * sizeof(long long int));
int *sz = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
uf[i] = i;
sz[i] = 1;
}

int count = n; // Keep track of number of roots or separate trees
for (int i = 0; i < l; i++) {
Union(uf, sz, pairs[i][0], pairs[i][1], &count);
}

// Find all roots and count the number of connection to root.
for (long long int i = 0; i < n; i++) {
sz[i] = 0;
}
for (long long int i = 0; i < n; i++) {
int p = Find(uf, i);
// uf[i] is not root but we searched to fidn root.
// increment count for root of tree which contains ith entry.
sz[p]++;
}

int *sums = (int *)malloc(n * sizeof(int));
for (long long int i = 0; i < n; i++) {
sums[i] = 0;
}
int sum = 0;
for (long long int i = n - 1; i >= 0; i--) {
if (sz[i] > 0) {
sums[i] = sum;
sum += sz[i];
}
}
ans = 0;
for (int i = 0; i < n; i++) {
// Search for countries.
if (sz[i] > 0) {
ans += (long long int)sz[i] * (long long int)sums[i];
}
}
printf("%lld\n", ans);
return(0);
}
```

{"mode":"full","isActive":false}