Day 028-Q3 | 並列二分探索（Parallel Binary Search）

問題

$N$ 頂点 $M$ 辺の重み付き無向グラフがある。辺を重みの昇順で追加していくとき、各クエリ $(u_i, v_i)$ に対して「$u_i$ と $v_i$ が初めて連結になる瞬間に追加された辺の重み」を求めよ。

入力形式

N M Q
u_1 v_1 w_1
...
u_M v_M w_M
q_1 r_1
...
q_Q r_Q

制約

$2 \le N \le 10^5$

$1 \le M \le 2 \times 10^5$

$1 \le Q \le 10^5$

$1 \le w_i \le 10^9$（全て異なる）

各クエリで $u_i$ と $v_i$ は最終的に連結

入出力例

入力例 1

出力例 1

4
5
3

ヒント (段階的開示)

ヒント1: 方向性

各クエリに対して独立に二分探索すると $O(Q \cdot M \cdot \alpha(N))$ かかる。並列二分探索なら $O(M \log M \cdot \alpha(N))$ に削減。

ヒント2: アプローチ

「辺を $x$ 本使ったとき $u_i, v_i$ は連結か」という単調述語。全クエリの現在の探索 mid でグルーピングし、一括で Union-Find 処理。

ヒント3: 誘導

lo = [0] * Q
hi = [M] * Q
for _ in range(ceil(log2(M))):
    buckets = defaultdict(list)
    for i in range(Q):
        if lo[i] < hi[i]:
            mid = (lo[i] + hi[i]) // 2
            buckets[mid].append(i)
    uf = UnionFind(N)
    for j in range(M):
        uf.unite(*edges[j])
        for i in buckets[j]:
            if uf.connected(q[i], r[i]): hi[i] = j
            else: lo[i] = j + 1

模範解答 (Python)

import sys
from collections import defaultdict
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def unite(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    N, M, Q = map(int, input().split())

    edges = []
    for _ in range(M):
        u, v, w = map(int, input().split())
        edges.append((w, u - 1, v - 1))
    edges.sort()

    queries = []
    for _ in range(Q):
        q, r = map(int, input().split())
        queries.append((q - 1, r - 1))

    lo = [0] * Q
    hi = [M] * Q

    from math import ceil, log2
    iterations = ceil(log2(M + 1)) + 1

    for _ in range(iterations):
        buckets = defaultdict(list)
        active = False
        for i in range(Q):
            if lo[i] < hi[i]:
                mid = (lo[i] + hi[i]) // 2
                buckets[mid].append(i)
                active = True

        if not active:
            break

        uf = UnionFind(N)
        for j in range(M):
            w, u, v = edges[j]
            uf.unite(u, v)

            if j in buckets:
                for i in buckets[j]:
                    qu, qv = queries[i]
                    if uf.connected(qu, qv):
                        hi[i] = j
                    else:
                        lo[i] = j + 1

    results = []
    for i in range(Q):
        results.append(edges[lo[i]][0])

    print('\n'.join(map(str, results)))

solve()

Step-by-Step 解説

1単調性
「辺を $x$ 本追加したとき連結か」は単調。二分探索可能。

2素朴解の遅さ
各クエリ独立: $O(Q M \log M \alpha(N))$ で TLE。

3並列化
全クエリを mid でバケツ分け。各反復で Union-Find を1回だけ再構築し、mid 通過時に一括判定。1反復 $O(M\alpha + Q)$。

4実装の注意点
イテレーション数は $\lceil \log_2(M+1)\rceil + 1$ に余裕を持つ。Union-Find は各反復で再構築。1-indexed/0-indexed の変換に注意。

5応用
時系列で変化するグラフ上のクエリ、オフライン処理可能なクエリ群に有効。

よくあるミス

ミス	原因	正しい書き方
イテレーション数不足	`log2(M)` の切り捨て	`ceil(log2(M+1))+1` か固定 25 回
バケツに M を入れる	hi=M で mid=M がバケツ空	hi 初期値とループ範囲を整合
lo==hi で収束しない	終了条件抜け	`active` フラグで早期終了
Union-Find リセット忘れ	前状態が混入	各反復先頭で `uf = UnionFind(N)`
1-indexed 混在	調整忘れ	`u-1, v-1` で変換

Day 028-Q3 — 並列二分探索（Parallel Binary Search）

問題