結果
問題 |
No.317 辺の追加
|
ユーザー |
![]() |
提出日時 | 2015-12-10 02:59:42 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,002 bytes |
コンパイル時間 | 477 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 36,224 KB |
最終ジャッジ日時 | 2024-09-15 07:22:14 |
合計ジャッジ時間 | 4,802 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 37 |
ソースコード
from collections import deque from sys import stdin, stdout, setrecursionlimit setrecursionlimit(10**6) 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() l = len(cs) dp = [n]*(n+1) def dfs(c, s, e): if c==l: return for i in xrange(c,l): cc = cs[i] if e < dp[s+cc]: dp[s+cc] = e+1 dfs(i+1, s+cc, e+1) dfs(0, 0, -1) for i in xrange(n): if dp[i]==n: dp[i] = -1 stdout.write("\n".join(map(str, dp[1:])) + "\n")