Cod sursa(job #1386092)

Utilizator rogoz.bogdanRogoz Bogdan rogoz.bogdan Data 12 martie 2015 18:07:08
Problema Cuplaj maxim in graf bipartit Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <fstream>
#include <vector>
#include <cstring>
#define NX 10001
#define MX 100001
using namespace std;

ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");
int n,m,e;
vector<int> v[NX];
bool viz[NX];
int match1[NX], match2[NX];

int match(int ind)
{
    if(viz[ind]) return 0;  //nodul ind s-a mai folosit
    viz[ind] = 1;

    vector<int>::iterator it;
    for(it=v[ind].begin(); it!=v[ind].end(); it++)
    {
        if(match2[*it] == 0)    //incercam sa il cuplam cu un nod adiacent liber
        {
            match1[ind] = *it;
            match2[*it] = ind;
            return 1;   //am reusit, ne intoarcem
        }
    }

    for(it=v[ind].begin(); it!=v[ind].end(); it++)
    {
        if(match(match2[*it]))  //incercam a doua oara sa eliberam un nod adiacent ocupat
        {
            match1[ind] = *it;
            match2[*it] = ind;
            return 1;
        }
    }

    return 0;
}

int main()
{
    int i,x,y;
    bool changed;
    fin>>n>>m>>e;

    for(i=1; i<=e; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }

    changed = 1;
    while(changed)  //s-a putut face o cuplare
    {
        changed = 0;
        memset(viz, 0, sizeof(viz));    //resetam vectorul de noduri vizitate

        for(i=1; i<=n; i++)
        {
            if(!match1[i]) changed = match(i);
        }
    }

    int matches = 0;
    for(i=1; i<=n; i++) matches += (match1[i] > 0);
    fout<<matches<<'\n';

    for(i=1; i<=n; i++)
    {
        if(match1[i]) fout<<i<<' '<<match1[i]<<'\n';
    }

    fin.close(); fout.close();
    return 0;
}