← 返回 akunacapital 的题目列表Maximum Difference Across Connected Components
类型：online_judge
Problem: Maximum Difference Across Connected Components
You are given an undirected graph with nodes labeled 1..gNodes. The edges are described by two lists gFrom[i] and gTo[i] (edge i connects gFrom[i] and gTo[i]).
For each connected component in the graph, compute:
maxNodeLabel - minNodeLabel
Return the maximum such value among all connected components.
Input
gNodes: number of nodes (labeled 1..gNodes)
gFrom: list/array of length gEdges
gTo: list/array of length gEdges
Output
An integer: the maximum difference over all connected components.
Constraints
1 <= gNodes <= 1e5
1 <= gEdges <= min(1e5, gNodes*(gNodes-1)/2)
Undirected graph; may be disconnected; isolated nodes may exist.
Example
gNodes = 4
gFrom = [1, 2]
gTo = [2, 3]
Connected components are {1,2,3} and {4}.
{1,2,3} diff = 3-1 = 2
{4} diff = 4-4 = 0
Output: 2
Example
Input
4 2
1 2
2 3
Output
2