結果
| 問題 | No.1744 Selfish Spies 1 (à la Princess' Perfectionism) |
| コンテスト | |
| ユーザー |
 convexineq
|
| 提出日時 | 2026-09-15 17:03:07 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 163 ms / 5,000 ms |
| + 595µs | |
| コード長 | 38,264 bytes |
| 記録 | |
| コンパイル時間 | 87 ms |
| コンパイル使用メモリ | 89,600 KB |
| 実行使用メモリ | 114,096 KB |
| 最終ジャッジ日時 | 2026-09-15 17:03:14 |
| 合計ジャッジ時間 | 6,011 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 39 |
ソースコード
# ===== BEGIN: /Suzlib/python/graph/BipartiteMatching.py =====
# competitive-verifier: TITLE 最大二部マッチング
from random import shuffle
class BipartiteMatching:
"""Kuhn 法を前処理に用いた Hopcroft--Karp 法。初回 solve の計算量は O((V + E) sqrt(V))。
辺番号を維持するため、削除済み辺も内部に保持する。
累積追加辺数を A とすると、辺情報の保持には O(A) の空間を使い、
edges は O(A)、matching_edge_ids は solve 後に O(V + A)、
CSR の再構築は O(V + A) 時間を要する。
"""
def __init__(self, n_left: int, n_right: int) -> None:
"""左右の頂点数を設定し、辺のない二部グラフと空のマッチングを作る。"""
assert 0 <= n_left
assert 0 <= n_right
self.n_left = n_left
self.n_right = n_right
self.g: list[list[int]] | None = None
self.mate_left = [-1] * n_left
self.mate_right = [-1] * n_right
self.size = 0
self._edge_shift = max(1, (n_right - 1).bit_length())
self._edge_mask = (1 << self._edge_shift) - 1
self._edges: list[int] = []
self._removed_edges: set[int] = set()
self._start: list[int] = []
self._to: list[int] = []
self._csr_built = False
self._solved = False
def add_edge(self, left: int, right: int) -> int:
"""solve 前に左頂点 left と右頂点 right を結ぶ辺を追加し、辺番号を返す。"""
if self._solved:
raise RuntimeError("call add_edge() before solve()")
assert 0 <= left < self.n_left
assert 0 <= right < self.n_right
edge_id = len(self._edges)
self._edges.append((left << self._edge_shift) | right)
return edge_id
def edge_count(self) -> int:
"""これまでに発行した辺番号の個数を返す。削除済み辺も数える。"""
return len(self._edges)
def edges(self) -> list[tuple[int, int, int]]:
"""現在存在する辺を (edge_id, left, right) で返す。"""
shift = self._edge_shift
mask = self._edge_mask
removed = self._removed_edges
return [
(edge_id, edge >> shift, edge & mask)
for edge_id, edge in enumerate(self._edges)
if edge_id not in removed
]
def _build_csr(self) -> None:
"""現在の辺を左頂点ごとの CSR にまとめる。再構築は累積追加辺数 A に対し O(V + A)。"""
if self._csr_built:
return
removed = self._removed_edges
if removed:
edges = [
edge
for edge_id, edge in enumerate(self._edges)
if edge_id not in removed
]
else:
edges = self._edges.copy()
shuffle(edges)
shift = self._edge_shift
mask = self._edge_mask
start = [0] * (self.n_left + 1)
for edge in edges:
start[(edge >> shift) + 1] += 1
for left in range(self.n_left):
start[left + 1] += start[left]
to = [0] * len(edges)
pos = start[:-1]
for edge in edges:
left = edge >> shift
to[pos[left]] = edge & mask
pos[left] += 1
self._start = start
self._to = to
self._csr_built = True
def _materialize_adjacency(self) -> None:
"""更新操作のため、必要になった時だけ可変な隣接リストを生成する。"""
if self.g is not None:
return
self._build_csr()
start = self._start
to = self._to
self.g = [
to[start[left]:start[left + 1]]
for left in range(self.n_left)
]
def _degree_greedy(self) -> int:
"""左右両側の CSR を用いて低次数頂点を優先した初期マッチングを構成する。"""
start = self._start
to = self._to
mate_left = self.mate_left
mate_right = self.mate_right
n_left = self.n_left
n_right = self.n_right
rstart = [0] * (n_right + 1)
for right in to:
rstart[right + 1] += 1
for right in range(n_right):
rstart[right + 1] += rstart[right]
rto = [0] * len(to)
pos = rstart[:-1]
for left in range(n_left):
for i in range(start[left], start[left + 1]):
right = to[i]
rto[pos[right]] = left
pos[right] += 1
degree_left = [start[left + 1] - start[left] for left in range(n_left)]
degree_right = [rstart[right + 1] - rstart[right] for right in range(n_right)]
leaves = [left for left in range(n_left) if degree_left[left] == 1]
leaves += [n_left + right for right in range(n_right) if degree_right[right] == 1]
twos = [left for left in range(n_left) if degree_left[left] == 2]
twos += [n_left + right for right in range(n_right) if degree_right[right] == 2]
added = 0
scan = 0
m = len(to)
while True:
while leaves:
v = leaves[-1]
degree = degree_left[v] if v < n_left else degree_right[v - n_left]
if degree == 1:
break
leaves.pop()
if leaves:
v = leaves.pop()
if v < n_left:
left = v
right = -1
for i in range(start[left], start[left + 1]):
w = to[i]
if degree_right[w]:
right = w
break
else:
right = v - n_left
left = -1
for i in range(rstart[right], rstart[right + 1]):
w = rto[i]
if degree_left[w]:
left = w
break
else:
while scan < n_left and degree_left[scan] == 0:
scan += 1
if scan == n_left:
break
while twos:
v = twos[-1]
degree = degree_left[v] if v < n_left else degree_right[v - n_left]
if degree == 2:
break
twos.pop()
v = twos.pop() if twos else scan
if v < n_left:
left = v
right = -1
best = m + 1
for i in range(start[left], start[left + 1]):
w = to[i]
degree = degree_right[w]
if 0 < degree < best:
right = w
best = degree
else:
right = v - n_left
left = -1
best = m + 1
for i in range(rstart[right], rstart[right + 1]):
w = rto[i]
degree = degree_left[w]
if 0 < degree < best:
left = w
best = degree
if left == -1 or right == -1:
continue
mate_left[left] = right
mate_right[right] = left
added += 1
degree_left[left] = 0
degree_right[right] = 0
for i in range(start[left], start[left + 1]):
w = to[i]
if degree_right[w]:
degree_right[w] -= 1
if degree_right[w] == 1:
leaves.append(n_left + w)
elif degree_right[w] == 2:
twos.append(n_left + w)
for i in range(rstart[right], rstart[right + 1]):
w = rto[i]
if degree_left[w]:
degree_left[w] -= 1
if degree_left[w] == 1:
leaves.append(w)
elif degree_left[w] == 2:
twos.append(w)
return added
def solve(self) -> int:
"""現在のグラフの最大マッチング数を返す。"""
if self._solved:
return self.size
self._build_csr()
start = self._start
to = self._to
mate_left = self.mate_left
mate_right = self.mate_right
if self.size == 0:
self.size = self._degree_greedy()
if self.size == 0:
self._solved = True
return 0
if self.size == min(self.n_left, self.n_right):
self._solved = True
return self.size
parent = [-1] * self.n_left
root = [-1] * self.n_left
queue = [0] * self.n_left
def kuhn_phase() -> int:
"""全未マッチ左頂点から交互森を伸ばし、増大路を貪欲に反転する。"""
q_tail = 0
for left in range(self.n_left):
parent[left] = -1
if mate_left[left] == -1:
parent[left] = -2
root[left] = left
queue[q_tail] = left
q_tail += 1
added = 0
q_front = 0
while q_front < q_tail:
left = queue[q_front]
q_front += 1
if mate_left[root[left]] != -1:
continue
matched_right = mate_left[left]
for i in range(start[left], start[left + 1]):
right = to[i]
if right == matched_right:
continue
next_left = mate_right[right]
if next_left == -1:
while left >= 0:
mate_right[right] = left
right, mate_left[left] = mate_left[left], right
left = parent[left]
added += 1
break
if parent[next_left] == -1:
parent[next_left] = left
root[next_left] = root[left]
queue[q_tail] = next_left
q_tail += 1
return added
for _ in range(128):
added = kuhn_phase()
self.size += added
if added == 0 or self.size == min(self.n_left, self.n_right):
self._solved = True
return self.size
del parent, root, queue
inf = self.n_left + 1
dist = [inf] * self.n_left
current_edge: list[int] = []
def bfs() -> int:
"""未マッチ左頂点から BFS し、最短増大路の長さを返す。"""
queue: list[int] = []
for left in range(self.n_left):
if mate_left[left] == -1:
dist[left] = 0
queue.append(left)
else:
dist[left] = inf
q_front = 0
while q_front < len(queue):
left = queue[q_front]
q_front += 1
next_dist = dist[left] + 1
for i in range(start[left], start[left + 1]):
right = to[i]
next_left = mate_right[right]
if next_left == -1:
return next_dist
if dist[next_left] == inf:
dist[next_left] = next_dist
queue.append(next_left)
return inf
def dfs(start_left: int, shortest: int) -> bool:
"""BFS 層に沿って最短増大路を1本探し、見つかれば反転する。"""
left = start_left
left_stack: list[int] = []
while True:
i = current_edge[left]
end = start[left + 1]
target = dist[left] + 1
while i < end:
right = to[i]
i += 1
next_left = mate_right[right]
if next_left == -1:
if target != shortest:
continue
current_edge[left] = i
while True:
mate_right[right] = left
right, mate_left[left] = mate_left[left], right
if right == -1:
return True
left = left_stack.pop()
if dist[next_left] == target:
current_edge[left] = i
left_stack.append(left)
left = next_left
break
else:
current_edge[left] = i
dist[left] = inf
if not left_stack:
return False
left = left_stack.pop()
while True:
shortest = bfs()
if shortest == inf:
break
current_edge = start[:-1]
for left in range(self.n_left):
if mate_left[left] == -1 and dfs(left, shortest):
self.size += 1
self._solved = True
return self.size
def _augment_once(self) -> bool:
"""全ての未マッチ左頂点から交互 BFS を1回だけ行い、増大路を1本だけ反転する。"""
self._materialize_adjacency()
assert self.g is not None
g = self.g
mate_left = self.mate_left
mate_right = self.mate_right
queue: list[int] = []
parent = [-1] * self.n_left
seen = [False] * self.n_left
for left in range(self.n_left):
if mate_left[left] == -1:
seen[left] = True
queue.append(left)
q_front = 0
while q_front < len(queue):
left = queue[q_front]
q_front += 1
matched_right = mate_left[left]
for right in g[left]:
if right == matched_right:
continue
next_left = mate_right[right]
if next_left == -1:
while right != -1:
mate_right[right] = left
right, mate_left[left] = mate_left[left], right
left = parent[left]
self.size += 1
return True
if not seen[next_left]:
seen[next_left] = True
parent[next_left] = left
queue.append(next_left)
return False
def increment_edge(self, left: int, right: int) -> bool:
"""最大マッチング構築後に辺を1本追加し、サイズが増えたかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before increment_edge()")
assert 0 <= left < self.n_left
assert 0 <= right < self.n_right
self._materialize_adjacency()
assert self.g is not None
self._edges.append((left << self._edge_shift) | right)
self.g[left].append(right)
self._csr_built = False
if self.size == min(self.n_left, self.n_right):
return False
if self.mate_left[left] == -1 and self.mate_right[right] == -1:
self.mate_left[left] = right
self.mate_right[right] = left
self.size += 1
return True
return self._augment_once()
def increment_edges_from_left(self, left: int, rights: list[int]) -> bool:
"""最大マッチング構築後に一つの左頂点から複数辺を追加し、サイズが増えたかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before increment_edges_from_left()")
assert 0 <= left < self.n_left
for right in rights:
assert 0 <= right < self.n_right
self._materialize_adjacency()
assert self.g is not None
base = left << self._edge_shift
self._edges.extend(base | right for right in rights)
self.g[left].extend(rights)
self._csr_built = False
if self.size == min(self.n_left, self.n_right):
return False
if self.mate_left[left] == -1:
for right in rights:
if self.mate_right[right] == -1:
self.mate_left[left] = right
self.mate_right[right] = left
self.size += 1
return True
return self._augment_once()
def increment_edges_from_right(self, right: int, lefts: list[int]) -> bool:
"""最大マッチング構築後に一つの右頂点へ複数辺を追加し、サイズが増えたかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before increment_edges_from_right()")
assert 0 <= right < self.n_right
for left in lefts:
assert 0 <= left < self.n_left
self._materialize_adjacency()
assert self.g is not None
for left in lefts:
self._edges.append((left << self._edge_shift) | right)
self.g[left].append(right)
self._csr_built = False
if self.size == min(self.n_left, self.n_right):
return False
if self.mate_right[right] == -1:
for left in lefts:
if self.mate_left[left] == -1:
self.mate_left[left] = right
self.mate_right[right] = left
self.size += 1
return True
return self._augment_once()
def remove_edge(self, edge_id: int) -> bool:
"""最大マッチング構築後に辺番号 edge_id の辺を削除し、最大マッチング数が減ったかを返す。"""
if not self._solved:
raise RuntimeError("call solve() before remove_edge()")
assert 0 <= edge_id < len(self._edges)
if edge_id in self._removed_edges:
raise ValueError("edge is already removed")
self._materialize_adjacency()
assert self.g is not None
edge = self._edges[edge_id]
left = edge >> self._edge_shift
right = edge & self._edge_mask
self._removed_edges.add(edge_id)
self.g[left].remove(right)
self._csr_built = False
if self.mate_left[left] != right:
return False
self.mate_left[left] = -1
self.mate_right[right] = -1
self.size -= 1
return not self._augment_once()
def matching_edges(self) -> list[tuple[int, int]]:
"""最大マッチングに使われる (左頂点, 右頂点) を返す。"""
self.solve()
return [
(left, right)
for left, right in enumerate(self.mate_left)
if right != -1
]
def matching_edge_ids(self) -> list[int]:
"""最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。"""
self.solve()
edge_for_left = [-1] * self.n_left
shift = self._edge_shift
mask = self._edge_mask
removed = self._removed_edges
for edge_id, edge in enumerate(self._edges):
if edge_id in removed:
continue
left = edge >> shift
if edge_for_left[left] != -1:
continue
right = edge & mask
if self.mate_left[left] == right:
edge_for_left[left] = edge_id
return [edge_id for edge_id in edge_for_left if edge_id != -1]
def mates(self) -> tuple[list[int], list[int]]:
"""左から右、右から左への対応をそれぞれ返す。未対応は -1。"""
self.solve()
return self.mate_left.copy(), self.mate_right.copy()
def _reachable_sets(self) -> tuple[list[bool], list[bool]]:
"""未マッチ左頂点から交互路で到達可能な左右の頂点集合を返す。"""
self.solve()
self._build_csr()
start = self._start
to = self._to
seen_left = [False] * self.n_left
seen_right = [False] * self.n_right
queue: list[int] = []
for left in range(self.n_left):
if self.mate_left[left] == -1:
seen_left[left] = True
queue.append(left)
q_front = 0
while q_front < len(queue):
left = queue[q_front]
q_front += 1
matched_right = self.mate_left[left]
for i in range(start[left], start[left + 1]):
right = to[i]
if right == matched_right or seen_right[right]:
continue
seen_right[right] = True
next_left = self.mate_right[right]
if next_left != -1 and not seen_left[next_left]:
seen_left[next_left] = True
queue.append(next_left)
return seen_left, seen_right
def min_vertex_cover(self) -> tuple[list[int], list[int]]:
"""最小頂点被覆を (左頂点列, 右頂点列) で返す。"""
seen_left, seen_right = self._reachable_sets()
left = [v for v in range(self.n_left) if not seen_left[v]]
right = [v for v in range(self.n_right) if seen_right[v]]
return left, right
def max_independent_set(self) -> tuple[list[int], list[int]]:
"""最大独立集合を (左頂点列, 右頂点列) で返す。"""
seen_left, seen_right = self._reachable_sets()
left = [v for v in range(self.n_left) if seen_left[v]]
right = [v for v in range(self.n_right) if not seen_right[v]]
return left, right
class GeneralBipartiteMatching:
"""頂点を一つの整数空間で与え、自動で二部彩色する最大二部マッチング。"""
def __init__(self, n: int) -> None:
"""n 頂点の空の辺列と、未彩色・未マッチの状態を初期化する。"""
assert 0 <= n
self.n = n
self.edges: list[tuple[int, int]] = []
self.color = [-1] * n
self.toL = [-1] * n
self.toR = [-1] * n
self.fromL: list[int] = []
self.fromR: list[int] = []
self.mateL: list[int] = []
self.mateR: list[int] = []
self.mate = [-1] * n
self.size = 0
self._matching: BipartiteMatching | None = None
self._solved = False
def add_edge(self, u: int, v: int) -> int:
"""頂点 u, v を結ぶ辺を追加し、辺番号を返す。solve 後は彩色を含めて再構築する。"""
assert 0 <= u < self.n
assert 0 <= v < self.n
edge_id = len(self.edges)
self.edges.append((u, v))
self._solved = False
return edge_id
def _bipartition(self) -> None:
"""現在の辺集合を二部彩色し、各頂点の色を self.color に保存する。"""
graph = [[] for _ in range(self.n)]
for u, v in self.edges:
graph[u].append(v)
graph[v].append(u)
color = [-1] * self.n
for start in range(self.n):
if color[start] != -1:
continue
color[start] = 1
queue = [start]
q_front = 0
while q_front < len(queue):
u = queue[q_front]
q_front += 1
next_color = color[u] ^ 1
for v in graph[u]:
if color[v] == -1:
color[v] = next_color
queue.append(v)
elif color[v] != next_color:
raise ValueError("graph is not bipartite")
self.color = color
def _build_lr(self) -> None:
"""二部彩色を左右に圧縮し、内部の BipartiteMatching を構築する。"""
self._bipartition()
self.fromL = [v for v in range(self.n) if self.color[v] == 0]
self.fromR = [v for v in range(self.n) if self.color[v] == 1]
self.toL = [-1] * self.n
self.toR = [-1] * self.n
for left, v in enumerate(self.fromL):
self.toL[v] = left
for right, v in enumerate(self.fromR):
self.toR[v] = right
matching = BipartiteMatching(len(self.fromL), len(self.fromR))
packed_edges: list[int] = []
shift = matching._edge_shift
for u, v in self.edges:
if self.color[u] == 0:
left = self.toL[u]
right = self.toR[v]
else:
left = self.toL[v]
right = self.toR[u]
packed_edges.append((left << shift) | right)
matching._edges = packed_edges
self._matching = matching
def solve(self) -> int:
"""現在のグラフの最大マッチング数を返す。非二部グラフなら ValueError。"""
if self._solved:
return self.size
self._build_lr()
assert self._matching is not None
self.size = self._matching.solve()
self.mateL = self._matching.mate_left
self.mateR = self._matching.mate_right
self.mate = [-1] * self.n
for left, right in enumerate(self.mateL):
if right == -1:
continue
u = self.fromL[left]
v = self.fromR[right]
self.mate[u] = v
self.mate[v] = u
self._solved = True
return self.size
def matching_edges(self) -> list[tuple[int, int]]:
"""最大マッチングを (色0の頂点, 色1の頂点) の組で返す。"""
self.solve()
return [
(self.fromL[left], self.fromR[right])
for left, right in enumerate(self.mateL)
if right != -1
]
def matching_edge_ids(self) -> list[int]:
"""最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。"""
self.solve()
assert self._matching is not None
return self._matching.matching_edge_ids()
def mates(self) -> list[int]:
"""各頂点の対応先を返す。未対応は -1。"""
self.solve()
return self.mate.copy()
def min_vertex_cover(self) -> list[int]:
"""元の頂点番号で最小頂点被覆を返す。"""
self.solve()
assert self._matching is not None
left, right = self._matching.min_vertex_cover()
return [self.fromL[v] for v in left] + [self.fromR[v] for v in right]
def max_independent_set(self) -> list[int]:
"""元の頂点番号で最大独立集合を返す。"""
self.solve()
assert self._matching is not None
left, right = self._matching.max_independent_set()
return [self.fromL[v] for v in left] + [self.fromR[v] for v in right]
# ===== END: /Suzlib/python/graph/BipartiteMatching.py =====
# ===== BEGIN: /Suzlib/python/graph/SCC.py =====
# competitive-verifier: TITLE 強連結成分分解 (SCC)
def find_SCC(g):
"""
グラフ g の SCC、各頂点の SCC 番号、縮約 DAG を返す。
SCC 番号はトポロジカル順で、縮約 DAG の多重辺は除く。
Gabow の path-based SCC algorithm を用いる。
"""
n = len(g)
SCC = []
S = [] # Gabow の active stack
P = [] # Gabow の root stack。S 上の根候補の位置を持つ
pos = [0] * n # 0: 未訪問, >0: S 上での位置, -1: SCC 確定済み
comp = [-1] * n
for i in range(n):
if comp[i] != -1:
continue
st = [i]
while st:
v = st.pop()
if v < 0: # 帰りがけ
v = ~v
d = pos[v] - 1
if P[-1] > d: # v が根候補として残っている
SCC.append(S[d:])
P.pop()
del S[d:]
c = len(SCC) - 1
for u in SCC[-1]:
pos[u] = -1
comp[u] = c
elif pos[v] > 0: # SCC 未確定の頂点への辺
while P[-1] > pos[v]:
P.pop()
elif pos[v] == 0: # 初訪問
S.append(v)
P.append(len(S))
pos[v] = len(S)
st.append(~v)
st += g[v]
k = len(SCC)
groups = SCC[::-1]
comp = [k - 1 - c for c in comp]
return groups, comp, condensation_graph(g, groups, comp)
def condensation_graph(g, groups, comp):
"""
SCC を縮約し、多重辺を除いた DAG の隣接リストを返す。
"""
k = len(groups)
dag = [[] for _ in range(k)]
seen = [-1] * k # seen[d] == c: SCC c から d への辺を追加済み
for c, vs in enumerate(groups):
for u in vs:
for v in g[u]:
d = comp[v]
if d != c and seen[d] != c:
seen[d] = c
dag[c].append(d)
return dag
# ===== END: /Suzlib/python/graph/SCC.py =====
# ===== BEGIN: /Suzlib/python/graph/BipartiteMatchingStructure.py =====
# competitive-verifier: TITLE 二部マッチングの構造
"""
DM分解、マッチングに使う辺・頂点
"""
# [bundled] from python.graph.BipartiteMatching import BipartiteMatching
# [bundled] from python.graph.SCC import find_SCC
REMOVED = -1
NEVER = 0
SOMETIMES = 1
ALWAYS = 2
def matching_structure(matching: BipartiteMatching) -> tuple[list[int], list[int], list[int]]:
"""
各辺・左頂点・右頂点が最大マッチングで
NEVER / SOMETIMES / ALWAYS のどれかを返す。
戻り値は (edge_status, left_status, right_status)。
edge_status は辺番号をそのまま添字に使い、削除済み辺は REMOVED とする。
"""
matching.solve()
n_left = matching.n_left
n_right = matching.n_right
s = n_left + n_right
t = s + 1
edges = matching.edges()
mate_left, mate_right = matching.mates()
matching_edge_ids = set(matching.matching_edge_ids())
g = [[] for _ in range(t + 1)]
# s -> left は容量 1。
for left, right in enumerate(mate_left):
if right == -1:
g[s].append(left)
else:
g[left].append(s)
# left -> right も容量 1。
# 現在のマッチング辺だけ逆向き、それ以外は順向きが残余辺になる。
for edge_id, left, right in edges:
r = n_left + right
if edge_id in matching_edge_ids:
g[r].append(left)
else:
g[left].append(r)
# right -> t は容量 1。
for right, left in enumerate(mate_right):
r = n_left + right
if left == -1:
g[r].append(t)
else:
g[t].append(r)
_, comp, _ = find_SCC(g)
edge_status = [REMOVED] * matching.edge_count()
for edge_id, left, right in edges:
r = n_left + right
if comp[left] == comp[r]:
edge_status[edge_id] = SOMETIMES
elif edge_id in matching_edge_ids:
edge_status[edge_id] = ALWAYS
else:
edge_status[edge_id] = NEVER
left_status = [NEVER] * n_left
for left, right in enumerate(mate_left):
if comp[s] == comp[left]:
left_status[left] = SOMETIMES
elif right != -1:
left_status[left] = ALWAYS
right_status = [NEVER] * n_right
for right, left in enumerate(mate_right):
r = n_left + right
if comp[r] == comp[t]:
right_status[right] = SOMETIMES
elif left != -1:
right_status[right] = ALWAYS
return edge_status, left_status, right_status
class DulmageMendelsohn:
"""
二部マッチングを容量 1, inf, 1 の s-t フローに読み替え、
全最小カットの構造から Dulmage--Mendelsohn 分解を求める。
頂点番号は左 0..n_left-1、右 n_left..n_left+n_right-1、
その後に s, t を置く。
DM 分解は
V0 : s から残余路で到達可能な固定領域
blocks : V0, Vinf の外側にある SCC
Vinf : t へ残余路で到達可能な固定領域
からなる。
groups = [V0] + blocks + [Vinf] とし、comp, dag もこの番号を使う。
残余グラフ自体の細かい SCC は scc_groups, scc_comp, scc_dag に残す。
"""
SOURCE = 0
FREE = 1
SINK = 2
def __init__(self, matching: BipartiteMatching) -> None:
"""最大マッチングから容量 1, inf, 1 の残余グラフを作り、DM 分解を求める。"""
matching.solve()
self.n_left = matching.n_left
self.n_right = matching.n_right
self.n = self.n_left + self.n_right
self.s = self.n
self.t = self.s + 1
self.edges = matching.edges()
self.mate_left, self.mate_right = matching.mates()
g = [[] for _ in range(self.t + 1)]
# s -> left は容量 1。
for left, right in enumerate(self.mate_left):
if right == -1:
g[self.s].append(left)
else:
g[left].append(self.s)
# left -> right は容量 inf なので、マッチング辺でも順向き残余辺が残る。
# マッチング辺にはさらに逆向き残余辺がある。
matched = set(matching.matching_edge_ids())
for edge_id, left, right in self.edges:
r = self.n_left + right
g[left].append(r)
if edge_id in matched:
g[r].append(left)
# right -> t は容量 1。
for right, left in enumerate(self.mate_right):
r = self.n_left + right
if left == -1:
g[r].append(self.t)
else:
g[self.t].append(r)
self.residual_graph = g
self.scc_groups, self.scc_comp, self.scc_dag = find_SCC(g)
k_scc = len(self.scc_groups)
s_scc = self.scc_comp[self.s]
t_scc = self.scc_comp[self.t]
# 最大流後なので s から t への残余路はない。
assert s_scc != t_scc
source_reachable = [False] * k_scc
stack = [s_scc]
source_reachable[s_scc] = True
while stack:
c = stack.pop()
for d in self.scc_dag[c]:
if not source_reachable[d]:
source_reachable[d] = True
stack.append(d)
rev = [[] for _ in range(k_scc)]
for c in range(k_scc):
for d in self.scc_dag[c]:
rev[d].append(c)
sink_reachable = [False] * k_scc
stack = [t_scc]
sink_reachable[t_scc] = True
while stack:
c = stack.pop()
for d in rev[c]:
if not sink_reachable[d]:
sink_reachable[d] = True
stack.append(d)
scc_state = [self.FREE] * k_scc
for c in range(k_scc):
if source_reachable[c]:
scc_state[c] = self.SOURCE
elif sink_reachable[c]:
scc_state[c] = self.SINK
self.scc_state = scc_state
# V0, Vinf は固定領域全体として一つにまとめ、自由領域だけ SCC を保つ。
free_scc = [c for c in range(k_scc) if scc_state[c] == self.FREE]
free_id = [-1] * k_scc
for i, c in enumerate(free_scc):
free_id[c] = i
self.V0 = [v for v in range(self.n) if scc_state[self.scc_comp[v]] == self.SOURCE]
self.blocks = [
[v for v in self.scc_groups[c] if v < self.n]
for c in free_scc
]
self.Vinf = [v for v in range(self.n) if scc_state[self.scc_comp[v]] == self.SINK]
k = len(self.blocks)
self.groups = [self.V0] + self.blocks + [self.Vinf]
self.s_comp = 0
self.t_comp = k + 1
dm_of_scc = [-1] * k_scc
for c in range(k_scc):
if scc_state[c] == self.SOURCE:
dm_of_scc[c] = self.s_comp
elif scc_state[c] == self.SINK:
dm_of_scc[c] = self.t_comp
else:
dm_of_scc[c] = 1 + free_id[c]
self.comp = [dm_of_scc[self.scc_comp[v]] for v in range(self.n)]
# V0 と Vinf をそれぞれ一頂点に縮約した DM の DAG。
dag = [[] for _ in range(k + 2)]
seen = [set() for _ in range(k + 2)]
for c in range(k_scc):
a = dm_of_scc[c]
for d in self.scc_dag[c]:
b = dm_of_scc[d]
if a != b and b not in seen[a]:
seen[a].add(b)
dag[a].append(b)
self.dag = dag
self.state = [self.SOURCE] + [self.FREE] * k + [self.SINK]
self.left_state = [self.state[self.comp[left]] for left in range(self.n_left)]
self.right_state = [
self.state[self.comp[self.n_left + right]]
for right in range(self.n_right)
]
# ===== END: /Suzlib/python/graph/BipartiteMatchingStructure.py =====
import sys
readline = sys.stdin.readline
# def solve():
# return
#
# T = int(readline())
# for _ in range(T):
# a = [int(i) for i in readline().split()]
# ans = solve()
# print(ans)
#n = int(readline())
#a = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range()]
#S = readline().strip()
#b = [readline().strip() for _ in range()]
n,m,L = [int(i) for i in readline().split()]
G = BipartiteMatching(n,m)
for _ in range(L):
a,b = [int(i) for i in readline().split()]
a -= 1
b -= 1
G.add_edge(a,b)
res = G.solve() # 最大マッチング
edge_status, left_status, right_status = matching_structure(G)
#print(edge_status)
#NEVER / SOMETIMES / ALWAYS
for v in edge_status:
if v == 2:
print("No")
else:
print("Yes")