Cod sursa(job #2184090)

Utilizator Athena99Anghel Anca Athena99 Data 23 martie 2018 18:27:48
Problema Cuplaj maxim in graf bipartit Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");

const int nmax= 10000;

int n, m, e;

bool u[nmax*2+1];
int p[nmax*2+1];

vector <int> g[nmax*2+1];

int pair_up( int x ) {
    if ( u[x]==0 ) {
        u[x]= 1;

        for ( vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it ) {
            if ( p[*it]==0 || pair_up(p[*it])==1 ) {
                p[x]= *it;
                p[*it]= x;

                return 1;
            }
        }
    }

    return 0;
}

int main(  ) {
    fin>>n>>m>>e;
    for ( int i= 1, x, y; i<=e; ++i ) {
        fin>>x>>y;

        g[x].push_back(n+y);
        g[n+y].push_back(x);
    }

    int sol= 0, ok= 1;
    while ( ok>0 ) {
        ok= 0;
        for ( int i= 1; i<=n; ++i ) {
            u[i]= 0;
        }

        for ( int i= 1; i<=n; ++i ) {
            if ( p[i]==0 ) {
                ok+= pair_up(i);
            }
        }

        sol+= ok;
    }

    fout<<sol<<"\n";
    for ( int i= 1; i<=n; ++i ) {
        if ( p[i]>0 ) {
            fout<<i<<" "<<p[i]-n<<"\n";
        }
    }

    return 0;
}