結果
問題 | No.1640 簡単な色塗り |
ユーザー |
![]() |
提出日時 | 2021-08-06 22:38:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 282 ms / 2,000 ms |
コード長 | 1,374 bytes |
コンパイル時間 | 129 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 106,288 KB |
最終ジャッジ日時 | 2024-06-29 15:40:44 |
合計ジャッジ時間 | 13,849 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
import sys input = sys.stdin.readline N = int(input()) class BipartiteMatching: def __init__(self, n, m): self._n = n self._m = m self._to = [[] for _ in range(n)] def add_edge(self, a, b): self._to[a].append(b) def solve(self): n, m, to = self._n, self._m, self._to pre = [-1] * n root = [-1] * n p = [-1] * n q = [-1] * m upd = True while upd: upd = False s = [] s_front = 0 for i in range(n): if p[i] == -1: root[i] = i s.append(i) while s_front < len(s): v = s[s_front] s_front += 1 if p[root[v]] != -1: continue for u in to[v]: if q[u] == -1: while u != -1: q[u] = v p[v], u = u, p[v] v = pre[v] upd = True break u = q[u] if pre[u] != -1: continue pre[u] = v root[u] = root[v] s.append(u) if upd: for i in range(n): pre[i] = -1 root[i] = -1 return [(v, p[v]) for v in range(n) if p[v] != -1] dinic = BipartiteMatching(N, N) for i in range(N): u, v = map(int, input().split()) u -= 1 v -= 1 dinic.add_edge(i, u) dinic.add_edge(i, v) flow = dinic.solve() if len(flow) == N: print("Yes") for _, x in flow: print(x + 1) else: print("No")