結果
問題 |
No.556 仁義なきサルたち
|
ユーザー |
![]() |
提出日時 | 2020-08-28 10:03:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 160 ms / 2,000 ms |
コード長 | 1,364 bytes |
コンパイル時間 | 464 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 77,824 KB |
最終ジャッジ日時 | 2024-11-09 01:07:55 |
合計ジャッジ時間 | 2,792 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import sys; input = sys.stdin.buffer.readline sys.setrecursionlimit(10**7) from collections import defaultdict con = 10 ** 9 + 7; INF = float("inf") def getlist(): return list(map(int, input().split())) class UnionFind: def __init__(self, n): self.par = [i for i in range(n + 1)] self.rank = [0] * (n + 1) self.size = [1] * (n + 1) def find(self, x): if self.par[x] == x: return x else: self.par[x] = self.find(self.par[x]) return self.par[x] def same_check(self, x, y): return self.find(x) == self.find(y) def union(self, x, y): x = self.find(x); y = self.find(y) if self.same_check(x, y) != True: if self.size[x] > self.size[y]: self.size[x] += self.size[y] self.size[y] = 0 self.par[y] = x elif self.size[x] < self.size[y]: self.size[y] += self.size[x] self.size[x] = 0 self.par[x] = y else: if x < y: self.size[x] += self.size[y] self.size[y] = 0 self.par[y] = x else: self.size[y] += self.size[x] self.size[x] = 0 self.par[x] = y def siz(self, x): x = self.find(x) return self.size[x] #処理内容 def main(): N, M = getlist() UF = UnionFind(N) for i in range(M): a, b = getlist() a -= 1; b -= 1 UF.union(a, b) for i in range(N): UF.par[i] = UF.find(i) for i in range(N): print(UF.par[i] + 1) if __name__ == '__main__': main()