結果

問題 No.317 辺の追加
ユーザー Tawara
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import defaultdict
N,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 x
for i in xrange(M):
u,v = map(lambda x:root(int(x)-1),raw_input().split())
parent[u] = v
for i in xrange(N):
conn_comp[root(i)] += 1
vertex_num = conn_comp.values()
vertex_num.sort(reverse=True)
prev = range(-1,N+1)
ans = [-1 for i in xrange(N+1)]
tmp_max = 0
for n in vertex_num:
dec = tmp_max = tmp_max + n
r = []
while dec > n:
if ans[dec] == -1:
if ans[dec-n] != -1:
ans[dec] = ans[dec-n] + 1
r.append(dec+1)
else:
for i in r:
prev[i] = dec
r = []
dec = prev[dec]
ans[n] = 0
for i in xrange(N):
print ans[i+1]
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0