1094. Connected Components After Edge Removals (Offline)

Given an undirected graph with n nodes and edges, and a list 'removals' of edge indices to remove one at a time in the given order, return the number of connected components after each removal. Solve it offline by processing removals in reverse. The input is JSON {n, edges, removals}.

Input: JSON {n, edges, removals}.

Output: Array — the component count after each removal.

Examples

Input: {"n":4,"edges":[[0,1],[1,2],[2,3]],"removals":[1,0,2]}
Output: [2,3,4]
Explanation: Components grow as edges are removed.

Input: {"n":3,"edges":[[0,1],[1,2]],"removals":[0]}
Output: [2]
Explanation: One removal splits a component.

Input: {"n":5,"edges":[[0,1],[1,2],[3,4]],"removals":[2,0,1]}
Output: [3,4,5]
Explanation: Removing 3-4 first splits that island, then the chain.

Constraints

• 1<=n<=10^5

Asked by