結果
問題 | No.2290 UnUnion Find |
ユーザー |
|
提出日時 | 2023-05-17 09:58:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 337 ms / 2,000 ms |
コード長 | 1,188 bytes |
コンパイル時間 | 428 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 108,672 KB |
最終ジャッジ日時 | 2024-12-15 05:24:50 |
合計ジャッジ時間 | 17,300 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
import sys input = sys.stdin.readline def main(): N, Q = map(int, input().split()) uf = UnionFind(N) ans = [] for _ in range(Q): query = list(map(int, input().split())) if query[0] == 1: u, v = query[1:] u, v = u - 1, v - 1 uf.union(u, v) else: v = query[1] - 1 ans.append(uf.ans(v)) print(*ans, sep='\n') class UnionFind: def __init__(self, n): self.parent = [-1] * n self.parents = set(range(n)) def find(self, x): if self.parent[x] < 0: return x self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): x, y = self.find(x), self.find(y) if x == y: return if self.parent[y] < self.parent[x]: x, y = y, x self.parent[x] += self.parent[y] self.parent[y] = x self.parents.discard(y) def same(self, x, y): return self.find(x) == self.find(y) def ans(self, y): x = self.find(y) for p in self.parents: if x != p: return p + 1 return -1 main()