結果

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