手抜き DSU
(src/data_structure/DSU.py)

• View this file on GitHub
• Last update: 2026-03-22 17:27:42+00:00

秒で実装したいときに使う Path Halving が非再帰で書きやすい

Verified with

• test/data_structure/DSU.test.py

Code

class DSU:
    def __init__(self, n):
        self.par = list(range(n))
    def find(self, x):
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x
    def unite(self, x, y):
        self.par[self.find(x)] = self.find(y)
    def same(self, x, y):
        return self.find(x) == self.find(y)

Traceback (most recent call last):
  File "/home/runner/work/ICPC_notebook/ICPC_notebook/.venv/lib/pypy3.11/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 "/home/runner/work/ICPC_notebook/ICPC_notebook/.venv/lib/pypy3.11/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page