Earliest Full Connectivity with Edge Removals
Problem statement
Process chronological logs [timestamp, operation, u, v] for an undirected social graph. Operation is ADD or REMOVE. All logs with the same timestamp take effect atomically.
Return the earliest timestamp after whose complete group all n users are connected. Duplicate additions and absent-edge removals are no-ops. Return -1 if this never occurs, and 0 for at most one user.
Function
firstFullyConnectedTimestamp(n: int, logs: String[][]) → longExamples
Example 1
n = 4logs = [["1","ADD","0","1"],["2","ADD","2","3"],["3","ADD","1","2"]]return = 3All four users first connect at timestamp 3.
Example 2
n = 3logs = [["1","ADD","0","1"],["2","ADD","1","2"],["2","REMOVE","0","1"]]return = -1The atomic timestamp-2 state is disconnected.
Example 3
n = 1logs = []return = 0One user is connected without an edge.
Constraints
0 <= n <= 2000.0 <= logs.length <= 2000.- Logs are sorted by nondecreasing timestamp.