結果

問題 No.2290 UnUnion Find
コンテスト
ユーザー Yukino DX.
提出日時 2024-09-13 22:17:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,271 bytes
コンパイル時間 383 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 85,120 KB
最終ジャッジ日時 2024-09-13 22:17:22
合計ジャッジ時間 6,221 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random


class UnionFindTree:
    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n
        self.sz = [1] * n

    def root(self, v):
        if self.par[v] == -1:
            return v
        self.par[v] = self.root(self.par[v])
        return self.par[v]

    def same(self, v1, v2):
        return self.root(v1) == self.root(v2)

    def size(self, v):
        return self.sz[self.root(v)]

    def unite(self, v1, v2):
        root1, root2 = self.root(v1), self.root(v2)
        if root1 == root2:
            return
        if self.rank[root1] < self.rank[root2]:
            root1, root2 = root2, root1
        self.par[root2] = root1
        if self.rank[root1] == self.rank[root2]:
            self.rank[root1] += 1
        self.sz[root1] += self.sz[root2]


n, q = map(int, input().split())
uf = UnionFindTree(n)
for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        u, v = query[1] - 1, query[2] - 1
        uf.unite(u, v)
    else:
        v = query[1] - 1
        if uf.size(v) == n:
            print(-1)
        else:
            while True:
                u = random.randrange(0, n)
                if not uf.same(u, v):
                    print(u + 1)
                    break
0