結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
|
提出日時 | 2024-02-27 07:00:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 745 ms / 2,000 ms |
コード長 | 1,422 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 111,232 KB |
最終ジャッジ日時 | 2024-09-29 11:54:59 |
合計ジャッジ時間 | 32,432 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
""" UnionFind """ class UnionFind(): def __init__(self, N): self.N = N self.parents = [-1] * N def find(self, x): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x): return -self.parents[self.find(x)] def same(self, x, y): return self.find(x) == self.find(y) N,Q = map(int, input().split()) vertex = set([i for i in range(N)]) UF = UnionFind(N) for q in range(Q): INPUT = list(map(int, input().split())) if INPUT[0] == 1: v1 = UF.find(INPUT[1]-1) v2 = UF.find(INPUT[2]-1) UF.union(INPUT[1]-1, INPUT[2]-1) if UF.find(INPUT[1]-1) == v1: vertex.discard(v2) else: vertex.discard(v1) else: if len(vertex) == 1: print(-1) else: v1,v2 = vertex.pop(), vertex.pop() if v1 == UF.find(INPUT[1]-1): print(v2+1) else: print(v1+1) vertex.add(v1) vertex.add(v2)