Hard · Offline DSU
Understand → Visualise → Practice.
Each log is `[time, a, b]`. Return the earliest time at which all n people are connected, or −1 if that never occurs.
Sort the logs by time and union the two people in each. The first time the component count drops to 1 is the answer.
Logs may arrive out of order.
Each union of different sets reduces the count by one.
Return the log's time when the count reaches 1; −1 if it never does.
O(e log e + e α(n)) time and O(n) space.
Processing the input order instead of chronological order can return a later time.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.