結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
![]() |
提出日時 | 2021-01-17 23:12:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 700 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 77,284 KB |
最終ジャッジ日時 | 2024-11-30 05:18:38 |
合計ジャッジ時間 | 2,797 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) N, M = map(int, input().split()) root = [-1] * N def find(x): if root[x] < 0: return x root[x] = find(root[x]) return root[x] def same(x, y): return find(x) == find(y) def merge(x, y): x = find(x) y = find(y) if x == y: return if root[x] == root[y]: x, y = min(x, y), max(x, y) root[x] += root[y] root[y] = x return if -root[x] < -root[y]: x, y = y, x root[x] += root[y] root[y] = x return for _ in range(M): a, b = map(int, input().split()) merge(a - 1, b - 1) for i in range(N): print(find(i) + 1)