Cod sursa(job #2851347)

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

const int INF = 1e9;

bool dfs(int x, vector<vector<int>>& G, vector<bool>& vis, vector<int>& pairOf){
    if(vis[x]){
        return false;
    }
    vis[x] = true;
    for(int y: G[x]){
        if(pairOf[y] == INF || dfs(pairOf[y], G, 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>> G(N + 1);
    int x, y;
    for(int i = 1; i <= E; ++i){
        cin >> x >> y;
        G[x].push_back(y);
    }

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

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

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