結果

問題 No.2072 Anatomy
ユーザー flygonflygon
提出日時 2022-09-16 22:21:36
言語 PyPy3
(7.3.8)
結果
AC  
実行時間 907 ms / 2,000 ms
コード長 529 bytes
コンパイル時間 280 ms
使用メモリ 139,932 KB
最終ジャッジ日時 2023-01-11 07:37:14
合計ジャッジ時間 16,418 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 104 ms
75,840 KB
testcase_01 AC 109 ms
76,704 KB
testcase_02 AC 116 ms
80,748 KB
testcase_03 AC 120 ms
81,296 KB
testcase_04 AC 111 ms
76,668 KB
testcase_05 AC 119 ms
81,132 KB
testcase_06 AC 112 ms
76,596 KB
testcase_07 AC 120 ms
81,700 KB
testcase_08 AC 885 ms
121,172 KB
testcase_09 AC 519 ms
127,556 KB
testcase_10 AC 739 ms
118,264 KB
testcase_11 AC 641 ms
128,944 KB
testcase_12 AC 515 ms
111,324 KB
testcase_13 AC 778 ms
122,820 KB
testcase_14 AC 635 ms
109,240 KB
testcase_15 AC 426 ms
112,908 KB
testcase_16 AC 807 ms
126,116 KB
testcase_17 AC 599 ms
122,748 KB
testcase_18 AC 404 ms
108,108 KB
testcase_19 AC 793 ms
126,656 KB
testcase_20 AC 907 ms
125,548 KB
testcase_21 AC 531 ms
139,776 KB
testcase_22 AC 797 ms
127,684 KB
testcase_23 AC 548 ms
139,680 KB
testcase_24 AC 532 ms
139,764 KB
testcase_25 AC 780 ms
125,596 KB
testcase_26 AC 103 ms
76,184 KB
testcase_27 AC 538 ms
139,932 KB
testcase_28 AC 748 ms
129,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m = map(int,input().split())
es = [list(map(int,input().split())) for i in range(m)]

p = [-1]*(n+1)
def find(x):
  if p[x] < 0:
    return x
  else:
    p[x] = find(p[x])
    return p[x]
def union(x,y):
  x = find(x)
  y = find(y)
  if x == y:
    return
  if p[x] > p[y]:
    x,y = y,x
  p[x] += p[y]
  p[y] = x

from collections import defaultdict
ps = defaultdict(int)
for i in range(m)[::-1]:
  u,v = es[i]
  uu,vv = find(u),find(v)
  mx = max(ps[uu],ps[vv])
  union(uu,vv)
  ps[find(uu)] = mx + 1

print(max(ps.values()))
0