Cod sursa(job #2241987)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 17 septembrie 2018 15:49:08
Problema Cuplaj maxim in graf bipartit Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 10005
using namespace std;
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");
int m, a,b, cuplat[nmax], m1[nmax], m2[nmax];
vector <int> v[nmax];

void citire()
{
    int k,i,j;
    f>>a>>b>>m;
    {
        for(k=1; k<=m; k++)
        {
            f>>i>>j;
            v[i].push_back(j);
        }
    }
}

int cuplaj(int nod)
{
    int j;
    if(cuplat[nod])
        return 0;
    cuplat[nod]=1;
    for(j=0; j<v[nod].size(); j++)
        if(!m1[v[nod][j]])
    {
        m1[v[nod][j]]=nod;
        m2[nod]=v[nod][j];
        return 1;
    }
    for(j=0; j<v[nod].size(); j++)
        if(cuplaj(m1[v[nod][j]]))
    {
        m1[v[nod][j]]=nod;
        m2[nod]=v[nod][j];
        return 1;
    }
    return 0;
}

int main()
{
    citire();
    int ok=1,i, nr=0;
    while(ok)
    {
        for(i=1; i<=a; i++)
            cuplat[i]=0;
        ok=0;
        for(i=1; i<=a; i++)
            if(!m2[i])
                if(cuplaj(i))
            {
                nr++;
                ok=1;
            }
    }
    g<<nr<<"\n";
    for(i=1; i<=a; i++)
    if(m2[i])
        g<<i<<m2[i]<<"\n";
    f.close();
    g.close();
    return 0;
}