1396번: 크루스칼의 공

https://www.acmicpc.net/problem/1396

$O(n+(m+q)\lg m)$

먼저 간선 e[0...m-1]을 가중치를 기준으로 오름차순 정렬한다.
그러면 각 (from, to) 쿼리에 대해
e[0...x]를 가지고 크루스칼 알고리즘을 통해 최소신장트리를 만들었을 때 from과 to가 같은 트리에 존재하는지 판정하는 결정문제로 바꿔 이진 검색으로 해결할 수 있다.
이제 다수의 쿼리를 빠르게 풀기 위해 Parallel Binary Search를 한다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct st {
    int x, y, z;
}e[100000];
int n, m, q, u[100000], v[100000], from[100000], to[100000], low[100000], up[100000], p[100001], sz[100001];
int par(int x) { return x^p[x] ? p[x] = par(p[x]) : x; }
vector<int> mid[100000];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
    sort(e, e + m, [](st l, st r) {
        return l.z < r.z;
    });
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d%d", from + i, to + i);
        low[i] = 0;
        up[i] = m - 1;
    }
    for (int i = m; i; i /= 2) {
        for (int j = 1; j <= n; j++) p[j] = j, sz[j] = 1;
        for (int j = 0; j < q; j++) mid[low[j] + up[j] >> 1].push_back(j);
        for (int j = 0; j < m; j++) {
            int x = par(e[j].x), y = par(e[j].y);
            if (x ^ y) p[y] = x, sz[x] += sz[y];
            for (auto it : mid[j]) {
                if (par(from[it]) ^ par(to[it])) low[it] = j + 1;
                else {
                    up[it] = j - 1;
                    u[it] = e[j].z;
                    v[it] = sz[x];
                }
            }
            mid[j].clear();
        }
    }
    for (int i = 0; i < q; i++) u[i] ? printf("%d %d\n", u[i], v[i]) : puts("-1");
    return 0;
}