Journey to the Moon (count invalid pairs)
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
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;}