Journey to the Moon (count invalid pairs)

Medium

Problem

Astronauts from the same country are linked by the given pairs (and transitively). Count the pairs of astronauts from different countries.

Example 1

Input:  n = 5, pairs = [[0,1], [2,3], [0,4]]
Output: 6

Countries {0,1,4} and {2,3}: 3 × 2 = 6.

Also asked as: Journey to the Moon

Test cases

Case 1

Input:    5, [[0,1],[2,3],[0,4]]
Expected: 6

Case 2

Input:    4, [[0,2]]
Expected: 5

Case 3

Input:    3, []
Expected: 3

Case 4

Input:    2, [[0,1]]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Union-Find component sizes, complement counting

Time O(N + P)Space O(N)

Same-country astronauts are one component. Valid pairs = total pairs − Σ (sizeᵢ choose 2).

function journeyToMoon(n, pairs) {
const parent = Array.from({ length: n }, (_, i) => i);
const size = new Array(n).fill(1);
const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
for (const [a, b] of pairs) {
const ra = find(a), rb = find(b);
if (ra !== rb) { parent[ra] = rb; size[rb] += size[ra]; }
}
let sumC2 = 0, done = new Set();
for (let i = 0; i < n; i++) {
const r = find(i);
if (done.has(r)) continue;
done.add(r);
sumC2 += (size[r] * (size[r] - 1)) / 2;
}
return (n * (n - 1)) / 2 - sumC2;
}