Earliest Time of Full Connectivity

Problem Statement

You are given an integer n representing the number of nodes in a network, labeled from 0 to n - 1. Initially, each node is isolated with no connections.

You are also given a list of connection events events, where each event is represented as a list of three integers [timestamp, u, v]. This indicates that at time timestamp, a bidirectional connection was formed between node u and node v.

Return the earliest timestamp at which the entire network becomes fully connected (i.e., every node can reach every other node through some sequence of connections). If the network never becomes fully connected, return -1.

Function Signature

def earliest_connectivity_time(n: int, events: list[list[int]]) -> int:
    pass

Constraints

• 2 <= n <= 10^5
• 1 <= len(events) <= 2 * 10^5
• events[i] = [timestamp, u, v]
• 0 <= timestamp <= 10^9
• 0 <= u, v < n and u != v
• The events are not guaranteed to be sorted by timestamp.
• Multiple edges between the same pair of nodes can occur at the same or different timestamps.

Examples

Example 1

Input: n = 4, events = [[20230101, 0, 1], [20230104, 2, 3], [20230102, 1, 2], [20230103, 0, 2]]
Output: 20230104
Explanation:
- Time 20230101: Node 0 and Node 1 connect. Components: {0, 1}, {2}, {3}.
- Time 20230102: Node 1 and Node 2 connect. Components: {0, 1, 2}, {3}.
- Time 20230103: Node 0 and Node 2 connect. They are already in the same component, so component count does not change.
- Time 20230104: Node 2 and Node 3 connect. All nodes {0, 1, 2, 3} are now connected. The earliest time is 20230104.

Example 2

Input: n = 4, events = [[5, 0, 1], [10, 1, 2]]
Output: -1
Explanation: Node 3 is never connected to any other node, so the graph is never fully connected.

Edge Cases

• Redundant edges that connect nodes already in the same component should not decrease the component count.
• Events with identical timestamps.
• Insufficient events to ever connect all nodes (len(events) < n - 1).