Java solution below. You can find connectedness of the astronauts by continually doing BFS searches until you've run out of 'unvisited' astronauts. Set up the astronaut pairs as an adjacency list (you can think of the pairs as undirected edges) and for each BFS search, add the number of astronauts you found to a list. After you have a list of country counts, it's just a little bit of math to find the number of possible pairs. Also, one test case requires a long output, so change the output type to that. public static long journeyToMoon(int n, List> astronaut) { // Write your code here // n = num astronauts int numPairs = astronaut.size();

// Build Adjacency List
List<Set<Integer>> pairList = new ArrayList<>();
for (int i = 0; i < n; i++) {
    pairList.add(new HashSet<>());
}
for (int i = 0; i < numPairs; i++) {
    int astronaut1 = astronaut.get(i).get(0);
    int astronaut2 = astronaut.get(i).get(1);
    pairList.get(astronaut1).add(astronaut2);
    pairList.get(astronaut2).add(astronaut1);
}
List<Integer> countryCounts = new ArrayList<>();

// Set up 'unvisited' set for BFS
Set<Integer> unvisited = new HashSet<>();
for (int i = 0; i < n; i++) {
    // This astronaut is the only one from a particular country
    if (pairList.get(i).size() == 0) { 
        countryCounts.add(1);
    } else {
        unvisited.add(i);
    }
}

// BFS to find connectedness of astronauts
// Store country counts
while(!unvisited.isEmpty()) {
    int firstAstronaut = unvisited.iterator().next();
    unvisited.remove(firstAstronaut);
    Queue<Integer> BFSqueue = new LinkedList<>();
    BFSqueue.add(firstAstronaut);
    int numAstroInCountry = 1;
    while(!BFSqueue.isEmpty()) {
        int currentAstro = BFSqueue.poll();
        for (Integer sameCountryAstro : pairList.get(currentAstro)) {
            if (unvisited.contains(sameCountryAstro)) {
                BFSqueue.add(sameCountryAstro);
                numAstroInCountry++;
                unvisited.remove(sameCountryAstro);
            }
        }
    }
    countryCounts.add(numAstroInCountry);
}
// Find Number of Pairs
int numCountries = countryCounts.size();
if (numCountries == 1) {
    return 0;
}
int possibleAstrosLeft = n;
long pairCount = 0;
for (int i = 0; i < numCountries; i++) {
    int numAstroInCountry = countryCounts.get(i);
    possibleAstrosLeft -= numAstroInCountry;
    if (possibleAstrosLeft == 0) {
        break;
    } 
    pairCount += numAstroInCountry * possibleAstrosLeft;
}
return pairCount;
}

}