結果
問題 | No.2072 Anatomy |
ユーザー |
|
提出日時 | 2022-09-16 21:52:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 466 ms / 2,000 ms |
コード長 | 2,418 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,528 KB |
実行使用メモリ | 99,380 KB |
最終ジャッジ日時 | 2024-12-21 19:09:38 |
合計ジャッジ時間 | 7,744 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
def main():from sys import stdin, setrecursionlimit# setrecursionlimit(1000000)input = stdin.readlinedef iinput(): return int(input())def sinput(): return input().rstrip()def i0input(): return int(input()) - 1def linput(): return list(input().split())def liinput(): return list(map(int, input().split()))def miinput(): return map(int, input().split())def li0input(): return list(map(lambda x: int(x) - 1, input().split()))def mi0input(): return map(lambda x: int(x) - 1, input().split())INF = 1000000000000000000MOD = 1000000007class UnionFindTree:def __init__(self, initial_size:int) -> None:self.n_nodes = initial_sizeself.parents = [i for i in range(initial_size)]self.ranks = [0 for i in range(initial_size)]self.size = [1 for i in range(initial_size)]self.n_roots = initial_sizedef root(self, n:int) -> int:if self.parents[n] == n:return nelse:self.parents[n] = self.root(self.parents[n])return self.parents[n]def same(self, n:int, m:int) -> bool:return (self.root(n) == self.root(m))def unite(self, n:int, m:int) -> None:if self.same(n, m):returnself.n_roots -= 1n, m = self.root(n), self.root(m)if self.ranks[n] < self.ranks[m]:self.parents[n] = mself.size[m] += self.size[n]else:self.parents[m] = nself.size[n] += self.size[m]if self.ranks[n] == self.ranks[m]:self.ranks[n] += 1def get_roots(self) -> set:return set([self.root(x) for x in range(self.n_nodes)])def count_roots(self) -> int:return self.n_rootsdef get_tree_size(self, n:int) -> int:return self.size[self.root(n)]N, M = miinput()uf = UnionFindTree(N)UV = []for _ in [0] * M:u, v = mi0input()UV.append((u, v))ctr = [0] * Nfor u, v in UV[::-1]:u = uf.root(u)v = uf.root(v)if u == v:ctr[u] += 1else:uf.unite(u, v)r = uf.root(u)ctr[r] = max(ctr[u], ctr[v]) + 1print(max(ctr))main()