Cod sursa(job #2851335)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 18 februarie 2022 14:15:40
Problema Cuplaj maxim in graf bipartit Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

bool dfs(int x, vector<vector<int>>& L, vector<vector<int>>& R,
         vector<bool>& vis, vector<int>& pairOf){
    if(vis[x]){
        return false;
    }
    vis[x] = true;
    for(int y: L[x]){
        if(pairOf[y] == INF || dfs(pairOf[y], L, R, vis, pairOf)){
            pairOf[y] = x;
            return true;
        }
    }
    return false;
}

int main(){
    ifstream cin("cuplaj.in");
    ofstream cout("cuplaj.out");

    int N, M, E;
    cin >> N >> M >> E;

    vector<vector<int>> L(N + 1);
    vector<vector<int>> R(M + 1);
    int x, y;
    for(int i = 1; i <= E; ++i){
        cin >> x >> y;
        L[x].push_back(y);
        R[y].push_back(x);
    }

    // pairOf[yNode]: xNode, if (xNode, yNode) is a matching edge
    //                INF, otherwise
    vector<bool> vis(N + 1);
    vector<int> pairOf(M + 1, INF);
    int matchingCard = 0;
    for(int x = 1; x <= N; ++x){
        fill(vis.begin(), vis.end(), false);
        matchingCard += (int)dfs(x, L, R, vis, pairOf);
    }

    cout << matchingCard << "\n";
    for(int y = 1; y <= M; ++y){
        if(pairOf[y] != INF){
            cout << pairOf[y] << " " << y << "\n";
        }
    }

    cin.close();
    cout.close();
    return 0;
}