We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here’s a step-by-step approach to solve this problem in PHP:
Model the Problem as a Graph:
Nodes are astronauts.
Edges connect astronauts from the same country.
Find Connected Components:
Use Depth-First Search (DFS) or Breadth-First Search (BFS) to find all connected components in the graph. Each connected component represents astronauts from the same country.
Calculate the Number of Valid Pairs:
Use the sizes of the connected components to determine the number of ways to choose pairs of astronauts from different countries.
Here's the PHP 5.6 solution:
<?phpfunctionjourneyToMoon($n,$astronaut){$graph=array_fill(0,$n,[]);// Build the graphforeach($astronautas$pair){$graph[$pair[0]][]=$pair[1];$graph[$pair[1]][]=$pair[0];}$visited=array_fill(0,$n,false);$components=[];// Function to perform DFS and find the size of each componentfunctiondfs($node,&$graph,&$visited,&$componentSize){$stack=[$node];while(!empty($stack)){$current=array_pop($stack);if(!$visited[$current]){$visited[$current]=true;$componentSize++;foreach($graph[$current]as$neighbor){if(!$visited[$neighbor]){$stack[]=$neighbor;}}}}}// Find all componentsfor($i=0;$i<$n;$i++){if(!$visited[$i]){$componentSize=0;dfs($i,$graph,$visited,$componentSize);$components[]=$componentSize;}}// Calculate the number of valid pairs$totalPairs=0;$sum=0;foreach($componentsas$size){$totalPairs+=$sum*$size;$sum+=$size;}return$totalPairs;}// Read input and execute the function$handle=fopen("php://stdin","r");fscanf($handle,"%d %d",$n,$p);$astronaut=[];for($i=0;$i<$p;$i++){fscanf($handle,"%d %d",$a,$b);$astronaut[]=[$a,$b];}$result=journeyToMoon($n,$astronaut);echo$result."\n";
Explanation:
Graph Construction:
An adjacency list is created to represent the graph.
Each pair of astronauts is added as an undirected edge in the graph.
Finding Connected Components:
A DFS function (dfs) is used to find the size of each connected component.
The DFS iterates over all nodes, and if a node hasn't been visited, it starts a new DFS to find all nodes in that component.
Calculating Valid Pairs:
The number of valid pairs is calculated by iterating over the sizes of the connected components.
For each component, the number of valid pairs that can be formed with astronauts from the current component and previously counted components is added to the total.
Usage:
This code reads from standard input, suitable for HackerRank's input format.
The graph is constructed, DFS is performed to find connected components, and finally, the number of valid pairs is calculated and printed.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Journey to the Moon
You are viewing a single comment's thread. Return to all comments →
Here’s a step-by-step approach to solve this problem in PHP:
Model the Problem as a Graph:
Find Connected Components:
Calculate the Number of Valid Pairs:
Here's the PHP 5.6 solution:
Explanation:
Graph Construction:
Finding Connected Components:
dfs
) is used to find the size of each connected component.Calculating Valid Pairs:
Usage: