Parallel Binary Search

Parallel binary search solves many monotone threshold searches together by sharing an expensive sequence of updates. “Parallel” refers to advancing multiple binary searches in rounds, not using CPU threads. Here edges are added to an initially empty undirected graph. For each queried pair, find the earliest prefix after which its vertices are connected. Connectivity is monotone under additions, so every query has one false-to-true threshold.

Prerequisites: Binary search invariants; Disjoint Set Union (DSU); offline processing. Difficulty: Advanced.

Build the idea

1. 1. Identify the monotone predicate

   For pair (u,v), P(k) means connected using only the first k edges. Once true it stays true because adding edges cannot disconnect anything. Deletions would invalidate this predicate and require a different technique. A vertex is connected to itself at k=0. Distinct vertices are initially disconnected. Never use binary search merely because the answer is an index; prove monotonicity first.

2. 2. Keep one search interval per query

   For distinct endpoints, low=0 is known false and high=m+1 is a sentinel that means “not yet known true; perhaps never.” The invariant is that the first true time, if any, lies in (low,high]. While low+1

3. 3. Bucket by midpoint and replay once

   In each round, group query IDs by their current mid. Create a fresh DSU, replay edges in chronological order, and evaluate bucket[k] immediately after adding edge k. Every test at k now sees exactly the same correct prefix. The DSU is rebuilt next round because queries may move their midpoints both forward and backward; ordinary DSU does not support undoing the last round’s state.

4. 4. Trace the sample

   Add (1,2), then (3,4), then (2,3). Pair (1,4) is false after two additions and true after three, so its answer is 3. Pair (1,2) is already connected after the first edge, answer 1. Pair (2,2) is connected before any additions, answer 0. During a round several queries may share midpoint 2, and all reuse the same DSU prefix rather than separately rebuilding it.

5. 5. See the advantage and limits

   Separate binary searches that rebuild a DSU for each tested prefix can replay O(qm log m) edges. Batched rounds replay only m edges each, plus q connectivity checks. There are O(log(m+1)) rounds because intervals halve independently. The technique applies whenever monotone queries can share a sweep or incremental state; the shared data structure need not be DSU. A persistent or rollback data structure can provide another approach with different tradeoffs.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<numeric>
#include<utility>
using namespace std;
struct DSU{
    vector<int>parent,size;
    DSU(int n):parent(n+1),size(n+1,1){
        iota(parent.begin(),parent.end(),0);
    }
    int find(int x){
        return parent[x]==x?x:parent[x]=find(parent[x]);
    }
    void unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return;
        }
        if(size[a]<size[b]){
            swap(a,b);
        }
        parent[b]=a;
        size[a]+=size[b];
    }
};
int main(){
    int n,m,q;
    if(!(cin>>n>>m>>q)){
        return 0;
    }
    vector<pair<int,int>>edges(m+1),queries(q);
    for(int i=1;i<=m;++i){
        cin>>edges[i].first>>edges[i].second;
    }
    vector<int>low(q,0),high(q,m+1);
    for(int i=0;i<q;++i){
        cin>>queries[i].first>>queries[i].second;
        if(queries[i].first==queries[i].second){
            high[i]=0; // Connected at time zero.
        }
    }
    for(;;){
        vector<vector<int>>bucket(m+1);
        bool pending=false;
        for(int i=0;i<q;++i){
            if(low[i]+1<high[i]){
                pending=true;
                bucket[(low[i]+high[i])/2].push_back(i);
            }
        }
        if(!pending){
            break;
        }
        DSU dsu(n); // Each round replays the update prefix from scratch.
        for(int time=1;time<=m;++time){
            dsu.unite(edges[time].first,edges[time].second);
            for(int id:bucket[time]){
                auto[u,v]=queries[id];
                if(dsu.find(u)==dsu.find(v)){
                    high[id]=time;
                }
                else{
                    low[id]=time;
                }
            }
        }
    }
    for(int answer:high){
        cout<<(answer==m+1?-1:answer)<<'\n';
    }
}

Complexity analysis

O((n+m+q) log(m+2) + (m+q)α(n) log(m+2)) is a safe full bound including DSU initialization and bucket setup each round; commonly O((n+(m+q)α(n)) log(m+1)). O(n+m+q) memory. n,m,q≤200000 is a typical scale. The inverse-Ackermann DSU cost is amortized over operations; queries are offline.

Example input and output

Read n m q, then m undirected edges in addition order, then q pairs u v (labels 1..n). Print the earliest prefix length when connected, 0 for identical vertices, or −1 if never connected. n≥1; m or q may be zero.

Input

4 3 3
1 2
3 4
2 3
1 4
1 2
2 2

Output

3
1
0

The third edge joins the two pairs into one component. The second query succeeds at edge 1, and the self-query succeeds at time zero.

Practical applications

Use for earliest connectivity, cumulative-resource thresholds and offline monotone update histories when many binary searches share replay work. For static undirected edge-addition connectivity, a union reconstruction tree plus LCA is another effective solution. Do not confuse parallel binary search with divide-and-conquer binary search over answers requiring a different update traversal.

Check your understanding

What work is shared across binary searches in a round?

Put it into practice

Test repeated edges, disconnected final graphs, m=0, and self-pairs.