#define PROBLEM "https://yukicoder.me/problems/no/1745" #include #include #include #include #include #include #include #include #include namespace suisen { struct BipartiteMatching { static constexpr int ABSENT = -1; BipartiteMatching() {} BipartiteMatching(int n, int m) : _n(n), _m(m), _to_r(_n, ABSENT), _to_l(_m, ABSENT), _g(n + m) {} void add_edge(int fr, int to) { _g[fr].push_back(to), _f = -1; } template int solve_heuristics() { if (_f >= 0) return _f; static std::mt19937 rng(std::random_device{}()); if constexpr (shuffle) for (auto& adj : _g) std::shuffle(adj.begin(), adj.end(), rng); std::vector vis(_n, false); auto dfs = [&, this](auto dfs, int u) -> bool { if (std::exchange(vis[u], true)) return false; for (int v : _g[u]) if (_to_l[v] == ABSENT) return _to_r[u] = v, _to_l[v] = u, true; for (int v : _g[u]) if (dfs(dfs, _to_l[v])) return _to_r[u] = v, _to_l[v] = u, true; return false; }; for (bool upd = true; std::exchange(upd, false);) { vis.assign(_n, false); for (int i = 0; i < _n; ++i) if (_to_r[i] == ABSENT) upd |= dfs(dfs, i); } return _f = _n - std::count(_to_r.begin(), _to_r.end(), ABSENT); } int solve_maxflow() { if (_f >= 0) return _f; const auto h = reversed_graph(); std::vector level(_n + _m), iter(_n + _m); std::deque que; auto bfs = [&] { for (int i = 0; i < _n; ++i) { if (_to_r[i] == ABSENT) level[i] = 0, que.push_back(i); else level[i] = -1; } std::fill(level.begin() + _n, level.end(), -1); bool ok = false; while (not que.empty()) { const int l = que.front(); que.pop_front(); for (int r : _g[l]) if (_to_r[l] != r and level[_n + r] < 0) { const int nl = _to_l[r]; level[_n + r] = level[l] + 1; if (nl == ABSENT) ok = true; else if (level[nl] < 0) level[nl] = level[l] + 2, que.push_back(nl); } } return ok; }; auto dfs = [&](auto dfs, const int r) -> bool { const int level_v = level[_n + r]; if (level_v < 0) return false; const int dr = h[r].size(); for (int &i = iter[_n + r]; i < dr; ++i) { const int l = h[r][i]; if (level_v <= level[l] or _to_l[r] == l or iter[l] > _m) continue; if (int nr = _to_r[l]; nr == ABSENT) { iter[l] = _m + 1, level[l] = _n + _m; _to_r[l] = r, _to_l[r] = l; return true; } else if (iter[l] <= nr) { iter[l] = nr + 1; if (level[l] > level[_n + nr] and dfs(dfs, nr)) { _to_r[l] = r, _to_l[r] = l; return true; } iter[l] = _m + 1, level[l] = _n + _m; } } return level[_n + r] = _n + _m, false; }; for (_f = 0; bfs();) { std::fill(iter.begin(), iter.end(), 0); for (int j = 0; j < _m; ++j) if (_to_l[j] == ABSENT) _f += dfs(dfs, j); } return _f; } int solve() { return solve_maxflow(); } std::vector> max_matching() { if (_f < 0) solve(); std::vector> res; res.reserve(_f); for (int i = 0; i < _n; ++i) if (_to_r[i] != ABSENT) res.emplace_back(i, _to_r[i]); return res; } std::vector> min_edge_cover() { auto res = max_matching(); std::vector vl(_n, false), vr(_n, false); for (const auto& [u, v] : res) vl[u] = vr[v] = true; for (int u = 0; u < _n; ++u) for (int v : _g[u]) if (not (vl[u] and vr[v])) { vl[u] = vr[v] = true; res.emplace_back(u, v); } return res; } std::vector min_vertex_cover() { if (_f < 0) solve(); std::vector> g(_n + _m); std::vector cl(_n, true), cr(_m, false); for (int u = 0; u < _n; ++u) for (int v : _g[u]) { if (_to_r[u] == v) { g[v + _n].push_back(u); cl[u] = false; } else { g[u].push_back(v + _n); } } std::vector vis(_n + _m, false); std::deque dq; for (int i = 0; i < _n; ++i) if (cl[i]) { dq.push_back(i); vis[i] = true; } while (dq.size()) { int u = dq.front(); dq.pop_front(); for (int v : g[u]) { if (vis[v]) continue; vis[v] = true; (v < _n ? cl[v] : cr[v - _n]) = true; dq.push_back(v); } } std::vector res; for (int i = 0; i < _n; ++i) if (not cl[i]) res.push_back(i); for (int i = 0; i < _m; ++i) if (cr[i]) res.push_back(_n + i); return res; } std::vector max_independent_set() { std::vector use(_n + _m, true); for (int v : min_vertex_cover()) use[v] = false; std::vector res; for (int i = 0; i < _n + _m; ++i) if (use[i]) res.push_back(i); return res; } int left_size() const { return _n; } int right_size() const { return _m; } std::pair size() const { return { _n, _m }; } int right(int l) const { assert(_f >= 0); return _to_r[l]; } int left(int r) const { assert(_f >= 0); return _to_l[r]; } const auto graph() const { return _g; } std::vector> reversed_graph() const { std::vector> h(_m); for (int i = 0; i < _n; ++i) for (int j : _g[i]) h[j].push_back(i); return h; } private: int _n, _m; std::vector _to_r, _to_l; std::vector> _g; int _f = 0; }; } // namespace suisen namespace suisen { std::vector, std::vector>> dulmage_mendelsohn_decomposition(BipartiteMatching& bm) { bm.solve(); const int n = bm.left_size(), m = bm.right_size(); std::vector wk_l(n, false), wk_r(m, false); const auto& g = bm.graph(); auto dfs_l = [&](auto dfs_l, int i) -> void { if (i == BipartiteMatching::ABSENT or std::exchange(wk_l[i], true)) return; for (int j : g[i]) wk_r[j] = true, dfs_l(dfs_l, bm.left(j)); }; for (int i = 0; i < n; ++i) if (bm.right(i) == BipartiteMatching::ABSENT) dfs_l(dfs_l, i); std::vector w0_l(n, false), w0_r(m, false); const auto h = bm.reversed_graph(); auto dfs_r = [&](auto dfs_r, int j) -> void { if (j == BipartiteMatching::ABSENT or std::exchange(w0_r[j], true)) return; for (int i : h[j]) w0_l[i] = true, dfs_r(dfs_r, bm.right(i)); }; for (int j = 0; j < m; ++j) if (bm.left(j) == BipartiteMatching::ABSENT) dfs_r(dfs_r, j); std::vector, std::vector>> dm; auto add_pair = [&](int i, int j) { auto& [l, r] = dm.back(); l.push_back(i), r.push_back(j); }; // W_0 dm.emplace_back(); for (int i = 0; i < n; ++i) if (w0_l[i]) { add_pair(i, bm.right(i)); } for (int j = 0; j < m; ++j) if (w0_r[j] and bm.left(j) == BipartiteMatching::ABSENT) { dm.back().second.push_back(j); } // W_1, ..., W_{k-1} atcoder::scc_graph scc_g(n + m); for (int i = 0; i < n; ++i) { for (int j : g[i]) scc_g.add_edge(i, n + j); int j = bm.right(i); if (j != BipartiteMatching::ABSENT) scc_g.add_edge(n + j, i); } for (const auto& group : scc_g.scc()) { if (int v0 = group.front(); (v0 < n and (w0_l[v0] or wk_l[v0])) or (v0 >= n and (w0_r[v0 - n] or wk_r[v0 - n]))) continue; dm.emplace_back(); for (int i : group) if (i < n) add_pair(i, bm.right(i)); } // W_k dm.emplace_back(); for (int j = 0; j < m; ++j) if (wk_r[j]) { add_pair(bm.left(j), j); } for (int i = 0; i < n; ++i) if (wk_l[i] and bm.right(i) == BipartiteMatching::ABSENT) { dm.back().first.push_back(i); } return dm; } } // namespace suisen using namespace suisen; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, l; std::cin >> n >> m >> l; std::vector> edges; BipartiteMatching bm(n, m); for (int i = 0; i < l; ++i) { int u, v; std::cin >> u >> v; --u, --v; bm.add_edge(u, v); edges.emplace_back(u, v); } auto bm_start = std::chrono::system_clock::now(); bm.solve(); auto bm_elapsed = std::chrono::duration_cast(std::chrono::system_clock::now() - bm_start).count(); auto dm_start = std::chrono::system_clock::now(); auto dm = dulmage_mendelsohn_decomposition(bm); auto dm_elapsed = std::chrono::duration_cast(std::chrono::system_clock::now() - dm_start).count(); std::cerr << "Matching : " << bm_elapsed << " ms\n"; std::cerr << "DM Decomp : " << dm_elapsed << " ms\n"; const int k = dm.size() - 1; std::vector cl(n), cr(m); for (int i = 0; i <= k; ++i) { for (int u : dm[i].first) cl[u] = i; for (int v : dm[i].second) cr[v] = i; } for (const auto &[u, v] : edges) { if (cl[u] != cr[v]) { std::cout << "No\n"; } else { std::cout << "Yes\n"; } } return 0; }