Parallel Binary Search with DSU
Parallel Binary Search with DSU Parallel binary search with DSU answers many offline connectivity queries over a sequence of edge insertions. It finds the earliest time when each pair of vertices becomes connected. The technique combines two ideas: parallel binary search over answer times disjoint set union for fast connectivity checks It applies when edges are only added. Once two vertices become connected, they remain connected, so the predicate is...