結果
問題 | No.2072 Anatomy |
ユーザー |
![]() |
提出日時 | 2022-09-22 20:46:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 719 ms / 2,000 ms |
コード長 | 933 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 132,992 KB |
最終ジャッジ日時 | 2024-12-22 05:04:03 |
合計ジャッジ時間 | 14,557 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
import sysinput=lambda:sys.stdin.readline().rstrip()class unionFind:def __init__(self,N):self.N=Nself.parent=[-1 for i in range(N)]self.size=[1 for i in range(N)]def find(self,x):path=[x]while self.parent[path[-1]]!=-1:path.append(self.parent[path[-1]])for i in path[:-1]:self.parent[i]=path[-1]return path[-1]def unite(self,x,y):roots=sorted([self.find(x),self.find(y)],key=lambda _:self.parent[_])if roots[0]!=roots[1]:self.parent[roots[0]]=roots[1]self.size[roots[1]]+=self.size[roots[0]]N,M=map(int,input().split())A=[list(map(lambda x:int(x)-1,input().split())) for i in range(M)][::-1]U=unionFind(N)mem={}for i in range(N):mem[U.find(i)]=0for i in A:temp=max(mem[U.find(i[0])],mem[U.find(i[1])])+1U.unite(i[0],i[1])mem[U.find(i[0])]=tempprint(max(mem.values()))