Hubs With the Shortest Longest Chain
Problem statement
A company has n departments, numbered 0 to n - 1. Each pair in edges is a direct reporting line between two departments, and together the lines form a tree.
If department h is chosen as the central hub, its longest chain is the largest number of reporting lines between h and any other department.
Return every department whose longest chain is as small as possible, in increasing order.
Function
findHubs(n: int, edges: int[][]) → int[]Examples
Example 1
n = 6edges = [[0,1],[1,2],[2,3],[2,4],[4,5]]return = [2]Department 2 is at most 2 reporting lines from everyone (2 → 1 → 0 and 2 → 4 → 5). Every other department has a chain of 3 or more to its farthest department, so the answer is [2].
Example 2
n = 4edges = [[3,2],[2,0],[0,1]]return = [0,2]The departments form a line 3 - 2 - 0 - 1. Both middle departments, 2 and 0, reach everyone within 2 lines: [0, 2].
Example 3
n = 1edges = []return = [0]With one department, it is the only hub and its longest chain is 0.
Constraints
1 <= n <= 2000edges.length == n - 1, eachedges[i] = [a, b]with0 <= a, b < nanda != b- The edges connect all departments into one tree (no repeated edge and no cycle).