Untitled
unknown
c_cpp
a year ago
1.0 kB
2
Indexable
#include <bits/stdc++.h> using namespace std; #define MAXN 505 vector<int> g[MAXN]; vector<int> match; vector<bool> used; bool try_kuhn(int v) { if (used[v]) return false; used[v] = true; for (auto to : g[v]) { if (match[to] == -1 || try_kuhn(match[to])) { match[to] = v; return true; } } return false; } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } match.assign(n, -1); for (int v = 0; v < n; ++v) { used.assign(n, false); try_kuhn(v); } int ans_cnt = 0; for (int i = 0; i < n; i++) if (match[i] != -1) ans_cnt++; cout << ans_cnt / 2 << '\n'; vector<bool> output(n, false); for (int i = 0; i < n; ++i) { if (match[i] != -1 && !output[i]) { output[match[i]] = true; printf("%d %d\n", match[i], i); } } }
Editor is loading...
Leave a Comment