提出 #58867147

---

ソースコード 拡げる

#LC UnionFind

class UnionFind:
    def __init__(self, N: int):
        assert 0 <= N < 1 << 31
        self._parent = [-1] * N  #負なら親で、要素数  正なら子で、ひとつ親の頂点番号
        self._next = [i for i in range(N)]  #同一連結成分の次の頂点番号
        self._direct = [i + 1 for i in range(N)]  #右側で最寄りの親  親の間のみ更新する
        self._Lt = 0  #暫定的な最左の親番号


    #頂点Viの親を探し、経路圧縮する
    def find(self, Vi: int):
        Pi = Vi
        #1. Viの親Piを探す
        while self._parent[Pi] >= 0:
            Pi = self._parent[Pi]

        #2. Vi → Piの経路上のすべての頂点に対し、親をPiに変更する
        while self._parent[Vi] >= 0:
            #parent[Vi] ← Pi(経路圧縮) と Vi ← parent[Vi](ひとつ親に移動) を同時に行う
            #代入順に注意！左辺は parent[Vi], Vi の順にすること(逆だと壊れる)
            self._parent[Vi], Vi = Pi, self._parent[Vi]
        return Pi


    def unite(self, Ui: int, Vi: int):
        #1. Ui, Viを親に置換しつつ、異なる連結成分かを評価
        if ( Ui := self.find(Ui) ) == ( Vi := self.find(Vi) ):
            return False

        #2. union by size  Uiがより大きいサイズの親になるようswapしてからマージ
        if self._parent[Ui] > self._parent[Vi]:
            Ui, Vi = Vi, Ui
        self._parent[Ui] += self._parent[Vi]
        self._parent[Vi] = Ui

        #3. connect(要素の列挙)用の配列をswap
        self._next[Ui], self._next[Vi] = self._next[Vi], self._next[Ui]
        return True


    def same(self, Ui: int, Vi: int):
        return self.find(Ui) == self.find(Vi)
    def size(self, Vi: int):
        return - self._parent[ self.find(Vi) ]


    #for v in self.connect(Vi): で、頂点Viの連結成分の要素を列挙する  Vi以降は順不同
    def connect(self, Vi: int):
        #1. 頂点Viを出力
        yield ( Pi := Vi )

        #2. 頂点Viに戻ってくるまで、次の頂点に移動
        while ( Pi := self._next[Pi] ) != Vi:
            yield Pi


    #for v in self.leader: で、親(代表値)を昇順に列挙  ならしO(親の数)
    @property
    def leader(self):
        #1. 最も番号の小さい親を探す
        while self._parent[ self._Lt ] >= 0:  #子なら
            self._Lt = self._direct[ self._Lt ]  #当時の記録を頼りに最寄りの親に移動

        #2. self._directの情報を更新しながら、超頂点Nまで移動
        back = now = self._Lt
        while now != N:
            #a) 次の頂点に移動する。Nに到達するか、親になったらbreak
            while ( now := self._direct[now] ) != N and self._parent[now] >= 0:
                pass

            #b) 親backから親nowの間には子しかないので、self._direct[back]を経路圧縮
            self._direct[back] = now

            #c) backを出力してから、back ← now
            yield back
            back = now



#入力高速化
import sys
input = sys.stdin.readline

#UnionFindを実行
N, Q = map(int, input().split())
UF = UnionFind(N)
for _ in range(Q):
    Ti, Ui, Vi = map(int, input().split())
    if Ti == 0: UF.unite(Ui, Vi)
    else: print(1 if UF.same(Ui, Vi) else 0)

提出情報

ジャッジ結果