結果
問題 | No.317 辺の追加 |
ユーザー |
![]() |
提出日時 | 2015-12-12 12:08:14 |
言語 | PyPy2 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 752 bytes |
コンパイル時間 | 468 ms |
コンパイル使用メモリ | 76,896 KB |
実行使用メモリ | 88,320 KB |
最終ジャッジ日時 | 2024-09-15 08:40:34 |
合計ジャッジ時間 | 4,589 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 37 |
ソースコード
from collections import defaultdictN,M = map(int,raw_input().split())parent = range(N)conn_comp = defaultdict(int)def root(x):while x != parent[x]:parent[x] = x = parent[parent[x]]return xfor i in xrange(M):u,v = map(lambda x:root(int(x)-1),raw_input().split())parent[u] = vfor i in xrange(N):conn_comp[root(i)] += 1vertex_num = conn_comp.values()vertex_num.sort(reverse=True)prev = range(-1,N+1)ans = [-1 for i in xrange(N+1)]tmp_max = 0for n in vertex_num:dec = tmp_max = tmp_max + nr = []while dec > n:if ans[dec] == -1:if ans[dec-n] != -1:ans[dec] = ans[dec-n] + 1r.append(dec+1)else:for i in r:prev[i] = decr = []dec = prev[dec]ans[n] = 0for i in xrange(N):print ans[i+1]