# Journey to the Moon

### Problem Statement :

```The member states of the UN are planning to send  people to the moon. They want them to be from different countries. You will be given a list of pairs of astronaut ID's. Each pair is made of astronauts from the same country. Determine how many pairs of astronauts from different countries they can choose from.

Function Description

Complete the journeyToMoon function in the editor below.

journeyToMoon has the following parameter(s):

int n: the number of astronauts
int astronaut[p]: each element  is a  element array that represents the ID's of two astronauts from the same country

Returns

- int: the number of valid pairs

Input Format

The first line contains two integers  and , the number of astronauts and the number of pairs.
Each of the next  lines contains  space-separated integers denoting astronaut ID's of two who share the same nationality.```

### Solution :

```                            ```Solution in C :

in  C :

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int FindP(int *P, int x) {
if(P[x] != x) {
P[x] = FindP(P, P[x]);
}
return P[x];
}

int MergeS(int *P, int *R, int *C, int A, int B) {
if(R[A] < R[B]) {
P[A] = B;
C[B] += C[A];
} else if(R[A] > R[B]) {
P[B] = A;
C[A] += C[B];
} else {
P[B] = A;
R[A] += 1;
C[A] += C[B];
}
}

int main() {
int R, P, C, i, N, I, A, B, UC;
int M, S;
unsigned long long result;
scanf("%d%d", &N, &I);
for(i=0;i<N;i++) {
P[i] = i;
C[i] = 1;
R[i] = 0;
}
for(i=0;i<I;i++) {
scanf("%d%d", &A, &B);
A = FindP(P, A);
B = FindP(P, B);
if(A != B)
MergeS(P, R, C, A, B);
}
UC = 0;
for(i=0;i<N;i++) {
if(P[i] == i) {
M[UC++] = C[i];
}
}
S = M;
for(i=1;i<UC;i++) {
S[i] = S[i-1] + M[i];
}
result = 0;
for(i=0;i<UC-1;i++) {
A = M[i];
B = S[UC-1] - S[i];
result += A*B;
}
printf("%llu", result);
return 0;
}```
```

```                        ```Solution in C++ :

In  C++ :

#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979

typedef long long Int;
typedef unsigned long long UInt;
typedef vector <int> VI;
typedef pair <int, int> PII;

VI a[1<<17];
bool was[1<<17];

int n,m;

int dfs(int cur)
{
if (was[cur])
return 0;

was[cur] = true;
int res = 1;

REP(i,SZ(a[cur]))
{
int nx = a[cur][i];

res += dfs(nx);
}

return res;
}

int main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);

scanf("%d%d",&n,&m);

REP(i,m)
{
int x,y;
scanf("%d%d",&x,&y);

a[x].push_back(y);
a[y].push_back(x);
}

VI all;

REP(i,n)
{
if (!was[i])
{
all.push_back(dfs(i));
}
}

Int res = 0;
Int sum = 0;
REP(i, SZ(all))
{
res += sum * all[i];

sum += all[i];
}

cout << res << endl;

return 0;
}```
```

```                        ```Solution in Java :

In  Java :

import static java.lang.Math.*;
import static java.util.Arrays.*;

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

public class Solution {

public static void main(String[] args) throws IOException {
new Solution().run();
}
StreamTokenizer in;
PrintWriter out;
//deb////////////////////////////////////////////////

public static void deb(String n, Object n1) {
System.out.println(n + " is : " + n1);
}

public static void deb(int[] A) {

for (Object oo : A) {
System.out.print(oo + " ");
}
System.out.println("");
}

public static void deb(long[] A) {

for (Object oo : A) {
System.out.print(oo + " ");
}
System.out.println("");
}

public static void deb(String[] A) {

for (Object oo : A) {
System.out.print(oo + " ");
}
System.out.println("");
}

public static void deb(int[][] A) {
for (int i = 0; i < A.length; i++) {
for (Object oo : A[i]) {
System.out.print(oo + " ");
}
System.out.println("");
}

}

public static void deb(long[][] A) {
for (int i = 0; i < A.length; i++) {
for (Object oo : A[i]) {
System.out.print(oo + " ");
}
System.out.println("");
}

}

public static void deb(String[][] A) {
for (int i = 0; i < A.length; i++) {
for (Object oo : A[i]) {
System.out.print(oo + " ");
}
System.out.println("");
}

}
/////////////////////////////////////////////////////////////

int nextInt() throws IOException {
in.nextToken();
return (int) in.nval;
}

long nextLong() throws IOException {
in.nextToken();
return (long) in.nval;
}

class Pair<X, Y> {

public X x;
public Y y;

public Pair(X x, Y y) {
this.x = x;
this.y = y;
}

public void setX(X x) {
this.x = x;
}

public void setY(Y y) {
this.y = y;
}
}

boolean inR(int x, int y) {
return (x >= 0) && (x < nn) && (y >= 0) && (y < nn);
}
static int nn;

void run() throws IOException {
//  out = new PrintWriter(new FileWriter("circles.out"));
out = new PrintWriter(new OutputStreamWriter(System.out));
solve();
out.flush();
}
static int[] parent; // n+1
static int count;
private void init() {
for (int i = 1; i < parent.length; i++) {
parent[i]=i;
}

}

private void union(int st, int en) {
int ss=par(st),ee=par(en);
if(ss!=ee){
parent[ss]=ee;
count--;
}

}

private int par(int th) {
if(parent[th]==th)return th;
else {
int k=par(parent[th]);
parent[th]=k;
return k;}
}
void solve() throws IOException {
int n = nextInt();
parent= new int[n+1];
init();
int l=nextInt();
for (int i = 0; i < l; i++) {
int a=nextInt(),b=nextInt();
union(a+1,b+1);
}
long[] A= new long[n+1];
for (int i = 1; i < n+1; i++) {
A[par(i)]++;
}

long ans=(long)n*(long)n;
for (int i = 1; i < n+1; i++) {
ans-=A[i]*A[i];
}
ans/=2;
System.out.println(ans);

}
}```
```

```                        ```Solution in Python :

In  Python3 :

#!/usr/bin/env python

import sys

if __name__ == '__main__':

# Count astronauts from different countries
astronauts = [-1] * N
countries = []

for _ in range(I):

if astronauts[A] > -1 and astronauts[B] > -1:
if astronauts[A] != astronauts[B]:
k = astronauts[B]
countries[astronauts[A]].extend(countries[k])

for i in countries[k]:
astronauts[i] = astronauts[A]
countries[k] = []

elif astronauts[A] > -1 and astronauts[B] == -1:
astronauts[B] = astronauts[A]
countries[astronauts[A]].append(B)

elif astronauts[A] == -1 and astronauts[B] > -1:
astronauts[A] = astronauts[B]
countries[astronauts[B]].append(A)

else:
astronauts[B] = astronauts[A] = len(countries)
countries.append([A, B])

# Count unpaired astronauts

# Count combinations
x = [len(c) for c in countries if c]

# Count the contributions from the unpaired astronauts
triangular_number = lambda n: n * (n + 1) // 2
unpaired = sum(x == -1 for x in astronauts)

total = triangular_number(unpaired - 1)
total += unpaired * sum(x)

for i in range(len(x) - 1):
for j in range(i + 1, len(x)):
total += x[i] * x[j]

print(total)```
```

## Find the Running Median

The median of a set of integers is the midpoint value of the data set for which an equal number of integers are less than and greater than the value. To find the median, you must first sort your set of integers in non-decreasing order, then: If your set contains an odd number of elements, the median is the middle element of the sorted sample. In the sorted set { 1, 2, 3 } , 2 is the median.

## Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

## Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

## Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

## Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

## Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and