cpl/graph/mst_kruskal.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from typing import List, Tuple

from cpl.data_structure.dsu import DSU


def mst_kruskal(N: int, edges: List[Tuple[int, int, int]]):
    edges = sorted(edges, key=lambda x: x[2])

    d = DSU(N)
    mst: List[Tuple[int, int, int]] = []
    sum_cost: int = 0
    for u, v, w in edges:
        if d.same(u, v):
            continue
        d.merge(u, v)
        mst.append((u, v, w))
        sum_cost += w
    return sum_cost, mst

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/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.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError