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 = sys.stdin.readline().split()
n, i = int(n), int(i)
prt = [-1 for k in range(n)]
for k in range(i):
a, b = sys.stdin.readline().split()
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)
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static void numSeclection(LinkedList<Integer>[] links){
int n = links.length;
int[] group = new int[n];
long[] count = new long[n+1];
LinkedList<Integer> q = new LinkedList();
q.add(0);
group[0] = 1; count[1] = 1;
int curGroup = 1;
int unassignedNode = 1;
while (!q.isEmpty()){
int cur = q.removeFirst();
for (int next:links[cur])
if (group[next]==0){
group[next] = curGroup;
q.add(next);
count[curGroup]++;
}
if (q.isEmpty()){
while(unassignedNode<n && group[unassignedNode]!=0) unassignedNode++;
if (unassignedNode<n){
curGroup++;
group[unassignedNode] = curGroup;
q.add(unassignedNode);
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();
LinkedList<Integer>[] links = new LinkedList[n];
for (int i=0; i<n; i++)
links[i] = new LinkedList();
for (int i=0; i<m; i++){
int x = sc.nextInt();
int y = sc.nextInt();
links[x].add(y);
links[y].add(x);
}
numSeclection(links);
}
}
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;
}
printf("%lld", answer);
}
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;
}
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("0n");
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("%lldn", ans);
return(0);
}