Parallel binary search

크루스칼의 공이라는 문제가 있다.

이 문제는 http://jason9319.tistory.com/280처럼 LCA를 이용하여 온라인 쿼리로 해결할 수 있으나 LCA를 쓰지않고 오프라인 쿼리로 해결 가능한 방법도 있다.

Parallel binary search는 이 문제를 오프라인 쿼리로 해결해 줄 방법이다.

어떤 문제가 요구하는 정답이 단조 증가의 모양을 가질 때 binary search를 이용한 parametric search로 답을 구해줄 수 있다.

크루스칼의 공같이 답이 될 수 있는 수가 연속적이라면 우리는 쿼리 전체에 대하여 binary search를 수행하여 답을 구해낼 수 있다.

하지만 쿼리 하나씩 이분 탐색을 거칠경우 너무 많은 시간이 소요되기 때문에

쿼리를 모아놓고 한번 값을 구할 때 해당값에 해당하는 모든 쿼리들을 다 계산해주는 방법을 사용할 것이다.

말로 표현하려니까 어려운데 소스코드를 직접 보는것이 이해가 쉬울 것이다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, q, x, y, z, lo[100010], hi[100010], p[100010], sz[100010], g[100010], rsz[100010];
pair<int, pair<int, int>> edge[100010];
pair<int, int> qry[100010];
vector<vector<int>> vt;
int find(int h){
    return h == p[h] ? h : p[h] = find(p[h]);
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y)return;
    p[x] = y;
    sz[y] += sz[x];
}
void init() {
    for (int i = 1; i <= n; i++)
        p[i] = i, sz[i] = 1;
    vt.clear();
    vt.resize(m + 2);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &edge[i].second.first, &edge[i].second.second, &edge[i].first);
    sort(edge + 1, edge + 1 + m);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d%d", &qry[i].first, &qry[i].second);
        lo[i] = 1, hi[i] = m + 1;
    }
    int f = 1;
    while (f) {
        f = 0;
        init();
        for (int i = 0; i < q; i++) {
            if (lo[i] < hi[i]) 
                vt[(lo[i] + hi[i]) >> 1].push_back(i);            
        }
        for (int i = 1; i <= m; i++) {
            merge(edge[i].second.first, edge[i].second.second);
            while (vt[i].size()) {
                f = 1;
                int idx = vt[i].back();
                vt[i].pop_back();
                if (find(qry[idx].first) == find(qry[idx].second)) {
                    hi[idx] = i;
                    g[idx] = edge[i].first;
                    rsz[idx] = sz[find(qry[idx].first)];
                }
                else
                    lo[idx] = i + 1;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (lo[i] == m + 1)
            puts("-1");
        else
            printf("%d %d\n", g[i], rsz[i]);
    }
    return 0;
}

while문에 들어가기 전까지의 소스는 모든 edge와 쿼리를 일단 저장해놓는다.

그리고 while문은 모든 쿼리에 대한 답이 구해질 때 까지 돌게 된다. 

while문이 한번 돌때마다 union find의 parent값들과 컴포넌트의 사이즈는 초기화된다.

자 이제 while문 안의 소스를 확인해보자

while (f) {
        f = 0;
        init();
        for (int i = 0; i < q; i++) {
            if (lo[i] < hi[i]) 
                vt[(lo[i] + hi[i]) >> 1].push_back(i);            
        }
        for (int i = 1; i <= m; i++) {
            merge(edge[i].second.first, edge[i].second.second);
            while (vt[i].size()) {
                f = 1;
                int idx = vt[i].back();
                vt[i].pop_back();
                if (find(qry[idx].first) == find(qry[idx].second)) {
                    hi[idx] = i;
                    g[idx] = edge[i].first;
                    rsz[idx] = sz[find(qry[idx].first)];
                }
                else
                    lo[idx] = i + 1;
            }
        }
    }

우선 모든 쿼리에 대해 mid값(답이 되는 간선의 번호)에 해당 쿼리가 존재한다고 삽입을 해준다.

그리고 m번째 간선을 처리해 줄 때(이 때 간선은 가중치 순서대로 정렬되어 있어야만 한다 -> 그래야만 현재 간선을 확인할 때 쿼리의 두 정점이 하나의 컴포넌트를 이룬다면 그 때의 값으로 해당 간선의 값을 매겨줄 수 있기 때문이다.) mid값으로 m을 가지는 모든 쿼리를 확인하여 준다(while vt[i].size 부분) 이 때 확인하는 쿼리의 두 컴포넌트가 결합되어 있는 경우 두 정점은 적어도 m번 간선이하의 간선을 확인할 때 합쳐지므로 hi값을 조절해야한다. 그리고 이때 답으로 출력할 간선의 최대 가중치와 컴포넌트의 크기를 입력해준다. 만약 쿼리의 두 컴포넌트가 분리되어 있다면 m번까지의 간선으로는 두 컴포넌트를 연결 시킬 수 없으므로 lo값을 증가시켜준다.

이러한 방식으로 바깥의 while문이 logM번 돌게 된다면 쿼리의 모든 값은 답이 구해진다.

이에 대한 정당성은 http://codeforces.com/blog/entry/45578 에 잘 설명되어있다.

전체에 쿼리에 대한 binary search를 QlogM번 수행하는것이 아닌 한번에 logM번에 처리해주는 것이 Parallel binary search의 핵심 포인트다.

연습문제로는 BOJ 8217 유성이 있다.