Cod sursa(job #2252185)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 2 octombrie 2018 14:06:12
Problema Cuplaj maxim in graf bipartit Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>

using namespace std;
int vizitateStanga[10001], vizitateDreapta[10001], viz[10001];
vector < int > graff[10001];
int n, m ,e, x, y;
bool k = true;

void visit(){
    for (int i = 1; i<= n; i++){
        viz[i] = 0;
    }
}

bool cuplare(int nod){
    if(viz[nod] == 1){
        k = false;
        return k;
    }
    viz[nod] = 1;

    /*if(vizitateStanga[nod] == 1){
        k = false;
        return k;
    }

    if(vizitateDreapta[nod] == 1){
        k = false;
        return k;
    }*/

    /* vizitateStanga[nod] = 1;
     * vizitateDreapta[nod] = 1;*/

    for (auto p : graff[nod]){
        if(vizitateDreapta[p] == 0){
            vizitateStanga[nod] = p;
            vizitateDreapta[p] = nod;
            k = true;
            return k;
        }
    }
    for (auto p : graff[nod]){
        if(cuplare(vizitateDreapta[p])){
            vizitateStanga[nod] = p;
            vizitateDreapta[p] = nod;
            k = true;
            return k;
            }
    }
    k = false;
    return k;
}

int main() {
    ifstream f("cuplaj.in");
    ofstream g("cuplaj.out");
    int nr = 0;
    f >> n >> m >> e;
    for (int i = 1; i <= e; i++){
        f >> x >> y;
        vizitateStanga[x] = 0;
        vizitateDreapta[y] = 0;
        graff[x].push_back(y);
    }


    while (k){
        k = false;
        visit();
        for (int i = 1; i <= n; i++){
            if(vizitateStanga[i] == 0){
                k |= cuplare(i);
            }
        }
    }

    for (int i = 1; i<= n; i++){
        if(vizitateStanga[i]){
            nr++;
        }
    }
    g << nr << "\n";

    for (int i = 1;  i <= n ; i++){
        if(vizitateStanga[i]){
            g << i << " " << vizitateStanga[i] << "\n";
        }
    }
    return 0;
}