HackerRank - Journey to the Moon
Solution⌗
- Graph is used to connect all astronauts to a country.
- Each cluster of graph represents a country.
- Each cluster is traversed to find the count of astronauts.
- Number of possible combinations are calculated based on sizes of these countries.
/* Solution to HackerRank: Journey to the Moon
* URL: https://www.hackerrank.com/challenges/journey-to-the-moon
*/
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
Graph graph = new Graph(N);
int P = in.nextInt();
for(int i = 0; i < P; i++){
int source = in.nextInt();
int destination = in.nextInt();
graph.addEdge(source,destination);
}
boolean[] visited = new boolean[N];
List<Integer> countries = new ArrayList<Integer>();
long combinations = 0;
// store size of each country by traversing each cluster
for(int i = 0; i < N; i++){
if(!visited[i]){
countries.add(graph.dfs(i, visited));
}
}
// calculating combinations with double caused test case #11 to timeout
/*for(int i = 0; i < clusters.size()-1; i++){
for (int j = i + 1; j < clusters.size(); j++){
combinations += clusters.get(i) * clusters.get(j);
}
}*/
/* Let size of each country be A, B, C, D ...
* Combinations: AB + AC + AD + BC + BD + CD + ...
* => AB + (A+B)C + (A+B+C)D
*/
int sum = 0;
for(int country : countries){
combinations += sum*country;
sum += country;
}
System.out.println(combinations);
}
}
class Graph{
List<Integer>[] vertices;
public Graph(int count){
vertices = new ArrayList[count];
for(int i = 0; i < count; i++){
vertices[i] = new ArrayList<Integer>();
}
}
public void addEdge(int source, int destination){
vertices[source].add(destination);
vertices[destination].add(source);
}
// modified DFS to return number of vertices traversed
public int dfs(int source, boolean[] visited){
visited[source] = true;
int count = 1;
for(Integer vertex: vertices[source]){
if(!visited[vertex]){
count += dfs(vertex, visited);
}
}
return count;
}
}
Read other posts
Discuss Post