사용자 도구

사이트 도구


ps:teflib:disjointset

disjointset.py

imports and globals

from typing import TypeVar

T = TypeVar('T')

DisjointSet

코드

# N DisjointSet
# I {"version": "2.0"}
class DisjointSet:
    """Disjoint Set for integers with path compression and union-by-size."""

    def __init__(self, size: int):
        self._parent = [-1] * size

    def union(self, x: int, y: int, should_raise: bool = False) -> int:
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            if should_raise:
                raise ValueError(f'{x} and {y} are already in the same set.')
            else:
                return root_x
        if self._parent[root_x] > self._parent[root_y]:
            root_x, root_y = root_y, root_x
        self._parent[root_x] += self._parent[root_y]
        self._parent[root_y] = root_x
        return root_x

    def find(self, x: int) -> int:
        while (p := self._parent[x]) >= 0:
            x, self._parent[x] = p, self._parent[p]
        return x

설명

이 코드를 사용하는 문제

출처문제 번호Page레벨
BOJ10775공항골드 2
BOJ10868최솟값골드 1
BOJ11085군사 이동골드 3
BOJ12893적의 적골드 4
BOJ13306트리플래티넘 5
BOJ15459Haybale Feast골드 1
BOJ16724피리 부는 사나이골드 2
BOJ1717집합의 표현골드 4
BOJ1976여행 가자골드 4
BOJ20040사이클 게임골드 4
BOJ23040누텔라 트리 (Easy)골드 3
BOJ23818원수의 원수골드 1
BOJ2927남극 탐험다이아몬드 5
BOJ4195친구 네트워크골드 2
BOJ4792레드 블루 스패닝 트리플래티넘 3
BOJ9938방 청소플래티넘 3

토론

댓글을 입력하세요:
Z A K​ S D
 
ps/teflib/disjointset.txt · 마지막으로 수정됨: 2022/11/11 16:01 저자 teferi