Cod sursa(job #3164379)

Utilizator cristiWTCristi Tanase cristiWT Data 2 noiembrie 2023 23:35:45
Problema Cuplaj maxim in graf bipartit Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
#define dbg(x) cerr << (#x) << ": " << x << "\n\n";
using namespace std;
const int NMAX = 1e4 + 5, MOD = 1e9 + 7;

bool viz[NMAX], deja[NMAX];
int n, m, e, mt[NMAX], sz;
vector<int> v[NMAX];

bool kuhn (int x)
{
    viz[x] = true;
    for (auto u : v[x])
        if (!viz[mt[u]] && (!mt[u] || kuhn(mt[u])))
        {
            mt[u] = x;
            deja[x] = true;
            return true;
        }
    return false;
}

signed main ()
{
#ifndef MOOLAMP
    freopen("cuplaj.in", "r", stdin);
    freopen("cuplaj.out", "w", stdout);
#endif
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> e;
    while (e--)
    {
        int x, y; cin >> x >> y;
        v[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        for (auto u : v[i])
            if (!mt[u])
            {
                sz++;
                mt[u] = i;
                deja[i] = true;
                break;
            }
    for (int i = 1; i <= n; i++)
        if (!deja[i])
        {
            memset(viz, false, sizeof(viz));
            sz += kuhn(i);
        }
    cout << sz << '\n';
    for (int i = 1; i <= m; i++)
        if (mt[i])
            cout << mt[i] << ' ' << i << '\n';
}