Cod sursa(job #2883803)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 1 aprilie 2022 20:34:02
Problema Cuplaj maxim in graf bipartit Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");
const int N=10001;
vector <int> a[N];
int n,m,pereche[N];
bool viz[N],cuplat[N];

int caut_cuplaj_ini(int x){
    for(auto y:a[x]){
        if(pereche[y]==0)
            return y;
    }
    return 0;
}

void init_viz(){
    for(int i=1; i<=m; i++)
        viz[i]=false;
}

bool incearca(int x){
    if(viz[x])
        return false;
    viz[x]=true;
    for(auto y:a[x]){
        if(pereche[y]==0 || incearca(pereche[y])){
            cuplat[x]=true;
            pereche[y]=x;
            return true;
        }
    }
    return false;
}

int main()
{
    int e;
    f>>m>>n>>e;
    for(int i=1; i<=e; i++){
        int x,y;
        f>>x>>y;
        a[x].push_back(y);
    }
    for(int i=1; i<=m; i++){
        int x=caut_cuplaj_ini(i);
        if(x!=0){
            pereche[x]=i;
            cuplat[i]=true;
        }
    }
    int l_cuplaj=0;
    bool imbunatatit;
    do{
        imbunatatit=false;
        init_viz();
        for(int i=1; i<=m; i++){
            if(!cuplat[i]){
                cuplat[i]=incearca(i);
                if(cuplat[i]){
                    imbunatatit=true;
                }
            }
        }
    }while(imbunatatit);
    for(int i=1; i<=n; i++)
        if(pereche[i]!=0)
            l_cuplaj++;
    g<<l_cuplaj<<'\n';
    for(int i=1; i<=n; i++)
        if(pereche[i]!=0)
            g<<pereche[i]<<' '<<i<<'\n';
    return 0;
}