Top-K Affinity Nodes in a Connected Component
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
You are given an undirected graph with nodes 0 through n-1. Node i has integer affinity affinity[i].
Find the connected component containing start, then return up to k node IDs from that component with highest affinity. Order the result by decreasing affinity, breaking ties by smaller node ID.
Duplicate edges and self-loops do not change the component. Return an empty array when k == 0.
Function
topAffinityNodes(n: int, edges: int[][], affinity: int[], start: int, k: int) → int[]Examples
Example 1
n = 6edges = [[0,1],[1,2],[3,4]]affinity = [5,9,7,100,50,8]start = 0k = 2return = [1,2]The component is {0,1,2}; nodes 1 and 2 have its two highest affinities.
Example 2
n = 4edges = [[0,1],[1,2],[2,3]]affinity = [4,4,4,4]start = 2k = 3return = [0,1,2]All affinities tie, so smaller node IDs come first.
Example 3
n = 3edges = []affinity = [8,2,5]start = 1k = 5return = [1]An isolated start node is a one-node component.
Constraints
1 <= n == affinity.length <= 200000.0 <= edges.length <= 300000.- Every edge endpoint is a valid node ID.
-10^9 <= affinity[i] <= 10^9.0 <= start < nand0 <= k <= n.