結果
問題 |
No.416 旅行会社
|
ユーザー |
![]() |
提出日時 | 2018-06-05 08:05:03 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 1,114 ms / 4,000 ms |
コード長 | 683 bytes |
コンパイル時間 | 453 ms |
コンパイル使用メモリ | 77,056 KB |
実行使用メモリ | 143,296 KB |
最終ジャッジ日時 | 2024-12-14 20:30:03 |
合計ジャッジ時間 | 13,086 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
from collections import * n, m, q = map(int, raw_input().split()) g = [set() for _ in xrange(n+1)] for _ in xrange(m): a, b = map(int, raw_input().split()) g[a].add(b) g[b].add(a) e = [] for _ in xrange(q): a, b = map(int, raw_input().split()) g[a].remove(b) g[b].remove(a) e.append((a,b)) g = [list(s) for s in g] r = [0]*(n+1) def bfs(i, x): q = deque([i]) while q: j = q.popleft() if r[j] != 0: continue r[j] = x q.extend(g[j]) bfs(1, -1) for i, j in e[::-1]: g[i].append(j) g[j].append(i) if not r[i]==r[j]==0: bfs(i, q) bfs(j, q) q -= 1 for i in r[2:]: print(i)