Problem Brief
Maximum Difference
FULLTIMEOA
Given a set of nodes and a set of edges between pairs of nodes, first identify the connected components in the graph. A connected component is a group of nodes that are all linked, either directly or through other nodes in the group.
For each connected component, calculate the difference between its largest and smallest node values, and return the maximum of these differences.
Function Description
Complete the function maximumDifference in the editor below.
maximumDifference has the following parameters:
int g_nodes: the number of nodes in the graphint g_from[g_edges]: one endpoint of each edgeint g_to[g_edges]: the other endpoint of each edge
Returns:
int: the maximum difference between the largest and smallest node value within any connected component
1Example 1
Input
g_nodes = 4, g_from = [1, 2], g_to = [2, 3]
Output
2
Explanation
Nodes 1, 2, and 3 form one connected component, whose difference is 3 - 1 = 2. Node 4 is isolated, so its component difference is 0. The maximum difference is 2.
2Example 2
Input
g_nodes = 6, g_from = [1, 2, 4], g_to = [2, 3, 6]
Output
2
Explanation
The connected components are {1, 2, 3}, {4, 6}, and {5}. Their differences are 2, 2, and 0, so the result is 2.
3Example 3
Input
g_nodes = 5, g_from = [1, 4], g_to = [5, 2]
Output
4
Explanation
The components are {1, 5}, {2, 4}, and {3}. Their differences are 4, 2, and 0, so the maximum difference is 4.
Constraints
Limits and guarantees your solution can rely on.
1 <= g_nodes <= 10^51 <= g_edges <= min(10^5, (g_nodes * (g_nodes - 1)) / 2)