Thawing Roads Parallel Search Problem

Thawing Roads Parallel Search Problem — ExecCode Hard DSA Practice

Solve the Thawing Roads Parallel Search problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Roads appear over time: edge [u, v, t] exists from time t onward (undirected). You start at village 0 and want the earliest time when every village is connected to every other (the whole graph is one component). Sort edges by time and union. Parallel binary search would answer a separate time per query village; here there is one global time. Return that time, or -1 if the villages never become fully connected. You are given: n — villages edges — [u, v, time] Return earliest time or -1. If n = 1 the answer is 0.

Examples

Input {'n': 3, 'edges': [[0, 1, 5], [1, 2, 8], [0, 2, 100]]}; Output 8. Input {'n': 2, 'edges': [[0, 1, 3]]}; Output 3. Input {'n': 3, 'edges': [[0, 1, 1]]}; Output -1

Constraints

Times are comparable integers Extra unused edges may exist

Practice Thawing Roads Parallel Search free on ExecCode. Browse DSA problems, topic map, and placement guides.