A logistics company runs a nationwide package-routing network with millions of daily scans. Each scan can introduce a “link” between two hubs (undirected). Over time, redundant links create cycles, which makes certain downstream processes (like deterministic route replay and auditing) harder.
Your job is to prune the network into a spanning forest (a tree per connected component) by removing edges that are redundant.
You are given:
n (number of hubs labeled 0..n-1)edges where each element is [u, v] representing an undirected link between hubs u and vReturn a list of edges to remove such that:
edges in the given order, you keep an edge if it connects two previously disconnected components.This produces a deterministic spanning forest consistent with the ingestion order.
Example 1
n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]][[2,0]][0,1] and [1,2], edge [2,0] connects nodes already connected, so it’s removed.Example 2
n = 6, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[0,2]][[2,0],[5,3],[0,2]][2,0] closes a cycle in component {0,1,2}; [5,3] closes a cycle in {3,4,5}; [0,2] is a parallel redundant edge and is removed when encountered.[].