Network Connectivity Timestamp

Sweep connection events in time order

For logs like (timestamp, a, b), sort by timestamp unless their order is guaranteed. Initialize a disjoint-set union structure with one component per person or machine. For each event, union the endpoints; decrement components only if their roots differed. The first timestamp at which components == 1 is the earliest time the network is fully connected.

Union-find with path compression and union by size makes each operation amortized O(alpha(n)), effectively constant, so total time is O(m log m + m alpha(n)) because sorting m logs dominates. Space is O(n). The invariant is that DSU components equal the connected components induced by all processed events. Test an already-single-node network, duplicate connections, self-links, logs that never connect everyone, and equal timestamps. Clarify whether simultaneous events are considered together; if so, process the timestamp group before deciding. A BFS after every event is correct but far too slow.