結果
問題 | 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.readlinesys.setrecursionlimit(10**7)from collections import defaultdictcon = 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 xelse: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] = 0self.par[y] = xelif self.size[x] < self.size[y]:self.size[y] += self.size[x]self.size[x] = 0self.par[x] = yelse:if x < y:self.size[x] += self.size[y]self.size[y] = 0self.par[y] = xelse:self.size[y] += self.size[x]self.size[x] = 0self.par[x] = ydef 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 -= 1UF.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()