Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int n, m, a, b, s, k;
- vector<vector<int> > lef;
- vector<int> righ;
- vector<int> used;
- bool dfs(int now) {
- if (used[now] == 1) {
- return false;
- }
- used[now] = 1;
- for (auto j : lef[now]) {
- if (righ[j] == -1 || dfs(righ[j])) {
- righ[j] = now;
- return true;
- }
- }
- return false;
- }
- int main() {
- cin >> n >> m >> k;
- lef.resize(n);
- righ.resize(m, -1);
- used.resize(n);
- for (int i = 0; i < k; i++) {
- cin >> a >> b;
- lef[a - 1].push_back(b - 1);
- }
- for (int i = 0; i < n; i++) {
- fill(used.begin(), used.end(), 0);
- dfs(i);
- }
- long long ans = 0;
- for (int i = 0; i < m; i++) {
- if (righ[i] != -1) {
- ans++;
- }
- }
- cout << ans << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment