DSL_1_A:Disjoint Set: Union Find Tree (続き2)

解説を読む

だいたいは似てるかなー
深さを覚えておいて浅くなるようにするところは自分よりまじめ

データが0始まりの整数の列に固定されてるのはちょっと気に入らないけど
競技プログラミングならそれで十分なのかも知れない
あるいは他のデータを使いたい場合は紐付けるって作戦なのかな

参考にしながら書き直してみる
やってることが似てる（かも）といっても構造が違うからかなり書き直し

このデータ構造、この前書いたみたいにほとんど要素だけで書けてしまうんだよな
集合としてのクラスはあんまりやることがなかったりする
こういうのはどう書くのがいいんだろう

と考えてみたけどテキスト通りの作りに

class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0

class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

    def _find_set(self, x):
        if x != self.elems[x].parent:
            self.elems[x].parent = self._find_set(self.elems[x].parent)
        return self.elems[x].parent

    def same(self, x, y):
        return self._find_set(x) == self._find_set(y)

    def _link(self, x, y):
        if self.elems[x].rank > self.elems[y].rank:
            self.elems[y].parent = x
        else:
            self.elems[x].parent = y
            if self.elems[x].rank == self.elems[y].rank:
                self.elems[y].rank += 1

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))

def main():
    n, q = [int(x) for x in input().split()]
    ds = DisjointSet(n)

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            ds.unite(x, y)
        else:
            print(1 if ds.same(x, y) else 0)

if __name__ == '__main__':
    main()

むー2倍くらい速くなった
さすがだ

しかしselfだらけだな
なんとかならないのか