結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
|
提出日時 | 2023-05-06 15:35:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 787 ms / 2,000 ms |
コード長 | 1,148 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 164,340 KB |
最終ジャッジ日時 | 2024-11-23 23:05:52 |
合計ジャッジ時間 | 34,856 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
N,Q = map(int,input().split()) parent = list(range(N)) import sys sys.setrecursionlimit(10 ** 8) s = set() q = list(range(N)) def find(i): if parent[i] == i:return i parent[i] = find(parent[i]) return parent[i] def unite(i,j): I = find(i) J = find(j) if I == J:return False s.add(I) parent[i] = J parent[I] = J return True for _ in range(Q): l = list(map(int,input().split())) if l[0] == 1: u,v = l[1],l[2] u -= 1 v -= 1 unite(u,v) else: u = l[1] u -= 1 if len(s) == N - 1: print(-1) else: a = -1 b = -1 while q: a = q.pop() if a in s:continue else:break while q: b = q.pop() if b in s:continue else:break if a >= 0 and b >= 0: U = find(u) if U == a:print(b + 1) else: print(a + 1) q.append(a) q.append(b) else: pass