結果

問題 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]
0