Binarization of Minimum Spanning Tree

概要

辺に重みがある\(N\)頂点からなるグラフ \(G\) の最小全域木\(T\)を求めた上で、木を頂点に重みがある二分木 \(U\) に変換する。

具体的には、グラフ\(G\)の\(N\)個の頂点に対応する頂点(番号\(1, 2, ..., N\))を用意し、グラフ\(G\)上においてKruskal法で2頂点をマージする順序に合わせて(\(i\)番目に頂点\(u_i, v_i\)を重み\(c_i\)の辺でマージするとする)、 頂点\(u_i, v_i\)をそれぞれ含む2つの二分木を子として持ち、新しい頂点(番号\(N+i\))を根頂点とする1つの二分木を生成する。(この時、新しい根頂点の重みを\(c_i\)とする)

そして、\(N-1\)回のマージによって最終的に1つの二分木 \(U\) を生成する。

この二分木 \(U\) は以下の特徴を持つ

  • \(2N - 1\) 個の頂点からなり、それぞれ \(1, 2, ..., N, N+1, ..., 2N-1\) の番号が付いている

  • 頂点\(2N - 1\) が根頂点となる

  • 二分木\(U\) の頂点\(v\) (\(1 \le v \le N\)) はMST \(T\)上の頂点 \(v\) と対応しており、二分木\(U\) の葉となる。

  • MST \(T\)の任意の頂点ペア\((u, v)\) (\(1 \le u, v \le N\))について、二分木 \(U\) 上の頂点 \(u\) と頂点 \(v\) のLCAとなる頂点の重みは MST \(T\)上の頂点 \(u, v\) 間のパスに含まれる辺の中の最大の重みになる

この二分木\(U\)上で二頂点のLCAを求められるようにすることで、MST上のある二頂点を繋ぐパス上の辺の重みの最大値が \(O(\log N)\) 等で求められる。

計算量

辺数を\(M\) とすると \(O(M \log M)\)

実装

# N: 頂点数
# E = [(c, a, b), ...]: 頂点aと頂点bを重みcの辺が繋ぐ
def binarization_mst(N, E):
    L = 2*N-1
    # G: 変換後の二分木
    G = [[] for i in range(L)]
    # W: 変換後の各頂点の重み
    W = [0]*L

    *p, = range(N)
    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(x)
        return y

    E.sort()

    cur = N
    *lb, = range(N)
    for c, a, b in E:
        pa = root(a); pb = root(b)
        if pa == pb:
            continue
        W[cur] = c
        G[cur] = [lb[a], lb[b]]
        if pa < pb:
            p[pb] = pa
            lb[pa] = cur
        else:
            p[pa] = pb
            lb[pb] = cur
        cur += 1
    # assert cur == L
    return G, W

Verified

  • AtCoder: "CODE FESTIVAL 2016 Elimination Tournament Round 1 - A問題: グラフ / Graph": source (Python3, 2965ms)