最小全域木 (ブルーフカ法)
(Graph/SpanningTree/boruvka.py)

• View this file on GitHub
• Last update: 2021-01-04 22:11:12+09:00

概要

ブルーフカ法により最小全域木の総コストを求める。

使い方

boruvka(n: int, edges: Iterable[Tuple[int, int, int]]) -> int
頂点数 n の無向グラフ $G=(V, E)$ に対して、重み付き辺集合 edges から構成される最小全域木の総コストを返す。計算量 $O(E\log V)$

Depends on

• Union Find (DataStructure/UnionFind/UnionFind.py)

Verified with

• TestCase/AOJ/GRL_2_A.boruvka.test.py

Code

from DataStructure.UnionFind.UnionFind import UnionFind


def boruvka(n, edges):
    INF = 10 ** 18
    uf = UnionFind(n)
    res = 0
    while uf.cnt != 1:
        update = False
        min_costs = [(INF, -1, -1) for _ in range(n)]
        for u, v, cost in edges:
            if not uf.same(u, v):
                rt_u = uf.root(v)
                rt_v = uf.root(u)
                min_costs[rt_u] = min(min_costs[rt_u], (cost, u, v))
                min_costs[rt_v] = min(min_costs[rt_v], (cost, u, v))
        for cost, u, v in min_costs:
            if cost != INF and not uf.same(u, v):
                update = True
                uf.merge(u, v)
                res += cost
        if not update:
            return -1
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page