結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2015-12-10 02:43:23 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 874 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 6,820 KB |
実行使用メモリ | 29,852 KB |
最終ジャッジ日時 | 2024-09-15 07:19:57 |
合計ジャッジ時間 | 4,429 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 37 |
ソースコード
from collections import deque from sys import stdin, stdout readline = stdin.readline inputs = lambda: map(int, readline().split()) n, m = inputs() g = [[] for i in xrange(n)] for i in xrange(m): u, v = inputs() u -= 1; v -= 1 g[u].append(v) g[v].append(u) cs = [] used = [0]*n for i in xrange(n): if not used[i]: deq = deque() used[i] = 1 cnt = 1 deq.append(i) while deq: v = deq.popleft() for t in g[v]: if not used[t]: used[t] = 1 deq.append(t) cnt += 1 cs.append(cnt) cs.sort() dp = [n]*(n+1) dp[0] = -1 s = 0 for c in cs: s += c for i in xrange(s,c-1,-1): dp[i] = min(dp[i], dp[i-c]+1) for i in xrange(n): if dp[i]==n: dp[i] = -1 stdout.write("\n".join(map(str, dp[1:])) + "\n")