Скачать или смотреть 3608. Minimum Time for K Connected Components | DSU + Binary search | weekly contest 457 - Q3

In this video, we solve the "Minimum Time for K Connected Components" problem using a binary search approach combined with Union-Find (Disjoint Set Union). The idea is to find the minimum time such that removing all edges with time less than or equal to t leaves at least k connected components in the graph.

We apply binary search on the range of edge times and for each mid-value, we simulate the graph by keeping only edges with time greater than mid, then count the connected components using the Union-Find data structure.

This method is both efficient and clean for handling dynamic connectivity problems.

Time Complexity:
O(E * α(N) * logM), where
E is the number of edges,
N is the number of nodes,
α(N) is the inverse Ackermann function (practically constant),
M is the range of edge times (max time - min time).

Space Complexity:
O(N), for parent and rank arrays used in Union-Find.