Uniformly sample edges to connect n connected components into one connected graph

You are given n connected undirected graphs G1, G2, ..., Gn whose vertex sets are pairwise disjoint. Implement a function sample_edges(graphs) that returns an additional set of edges E_add such that: After adding E_add to the union of all graphs, the overall graph becomes connected. E_add is sampled uniformly at random among all edge sets that satisfy (1), meaning every feasible E_add has the same probability of being returned. Assumptions: You may add an undirected edge between any two vertices belonging to different graphs (arbitrary cross-component edges). You may not add edges within the same Gi (every added edge must connect two different components). Provide a sampling algorithm (pseudo-code is fine) and analyze its time complexity. Input: the n graphs (e.g., as vertex lists, or just sizes s_i). Output: an edge list E_add, each edge is (u, v) with u and v from different components. Suggested constraints: 1 <= n <= 1e5 component sizes s_i, total vertices S = sum(s_i) up to 1e5 Note: The original post didn’t specify whether vertex sets are disjoint or the exact meaning of uniformity; this statement completes it as “uniform over feasible edge sets,” a common interview interpretation. Example Input n=2, component sizes: [2,3] Output One edge connecting any vertex in comp1 to any vertex in comp2 (uniform among 2*3 choices)