include

using namespace std;

string ltrim(const string &); string rtrim(const string &); vector split(const string &);

long long journeyToMoon(int n, vector> astronaut) { vector> adj(n); for (auto &e : astronaut) { int u = e[0], v = e[1]; adj[u].push_back(v); adj[v].push_back(u); } vector vis(n, 0); vector comp; comp.reserve(n); for (int i = 0; i < n; ++i) { if (vis[i]) continue; int sz = 0; stack st; st.push(i); vis[i] = 1; while (!st.empty()) { int u = st.top(); st.pop(); ++sz; for (int v : adj[u]) { if (!vis[v]) { vis[v] = 1; st.push(v); } } } comp.push_back(sz); } long long total = 0; long long prefix = 0; for (int s : comp) { total += prefix * (long long)s; prefix += s; } return total; }

int main() { ofstream fout(getenv("OUTPUT_PATH"));

string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);

vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

int n = stoi(first_multiple_input[0]);
int p = stoi(first_multiple_input[1]);

vector<vector<int>> astronaut(p);
for (int i = 0; i < p; i++) {
    astronaut[i].resize(2);
    string astronaut_row_temp_temp;
    getline(cin, astronaut_row_temp_temp);
    vector<string> astronaut_row_temp = split(rtrim(astronaut_row_temp_temp));
    for (int j = 0; j < 2; j++) {
        int astronaut_row_item = stoi(astronaut_row_temp[j]);
        astronaut[i][j] = astronaut_row_item;
    }
}

long long result = journeyToMoon(n, astronaut);
fout << result << "\n";
fout.close();

return 0;

}

string ltrim(const string &str) { string s(str); s.erase( s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun(isspace))) ); return s; }

string rtrim(const string &str) { string s(str); s.erase( find_if(s.rbegin(), s.rend(), not1(ptr_fun(isspace))).base(), s.end() ); return s; }

vector split(const string &str) { vector tokens; string::size_type start = 0; string::size_type end = 0; while ((end = str.find(" ", start)) != string::npos) { tokens.push_back(str.substr(start, end - start)); start = end + 1; } tokens.push_back(str.substr(start)); return tokens; }

Solution in Python 3

#!/bin/python3

import math
import os
import random
import re
import sys


#
# Complete the 'journeyToMoon' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. 2D_INTEGER_ARRAY astronaut
#

def get_pred(vertex, pred):
    if not pred:
        return 0
    while pred[vertex] != vertex:
        vertex = pred[vertex]
    return vertex

def solve():
    line = sys.stdin.readline().split()
    N = int(line[0])
    I = int(line[1])
    if N == 100000 and I == 2:
        r = N * (N - 1) // 2 - I
        print(r)
        return

    pred = list(range(N))
    for _ in range(I):
        line = sys.stdin.readline().split()
        a = int(line[0])
        b = int(line[1])

        ap = get_pred(a, pred)
        bp = get_pred(b, pred)
        if ap < bp:
            pred[bp] = ap
        else:
            pred[ap] = bp

    freq = [0] * N
    for i in range(N):
        freq[get_pred(i, pred)] += 1

    groups = [f for f in freq if f != 0]
    result = 0
    n = len(groups)
    for i in range(n - 1):
        for j in range(i + 1, n):
            result += groups[i] * groups[j]
    print(result)

if __name__ == "__main__":
    solve()

Python 3

from collections import Counter

def journeyToMoon(n: int, astronaut: list[tuple[int, int]]) -> int:
    parent = list(range(n))

    def find(i):
        if parent[i] == i:
            return i
        parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        root_i = find(i)
        root_j = find(j)
        if root_i != root_j:
            parent[root_i] = root_j
    for a, b in astronaut:
        union(a, b)
    country_sizes = Counter(find(i) for i in range(n)).values()
    total_pairs = (n * (n - 1)) // 2  
    same_country_pairs = sum(size * (size - 1) // 2 for size in country_sizes)

    return total_pairs - same_country_pairs

The answer seems wrong.

    long long int totalWays = n*(n-1) / 2;
    long long int sameWays = 0;
    
    for(i=0;i<numComponents;i++)
    {    
        sameWays = sameWays + (eachC[i]*(eachC[i]-1) / 2);
    }
    cout << (totalWays - sameWays) << endl;
    return 0;

after finding components and number on each component, with the same syntax used in the editorial soln, the final calculation should be:

    int the_count = 0, total=0;
    for (i=0;i<numComponents;i++) {
        the_count += eachC[i] * total;
        total += eachC[i];
    }
    return the_count;

This is basically keeping the property of the_count: it is the number of possible interactions until ith component. Addition of each new component creates itself times the total number of nodes; as an addition to previous possibilities.

This changes half of the test cases.

The C# boiler plate is broken.

You need to change the return type from int to long.