Cod sursa(job #2733801)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 30 martie 2021 22:22:11
Problema Cuplaj maxim in graf bipartit Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
const int NIL = 0;
const int INF = INT_MAX;
vector<int> gr[N];
int pU[N], pV[N];
int nrU, nrV;
int dist[N];
bool bfs_alter(){
  queue<int> q;
  for(int i = 1; i<=nrU; i++){
    if(pU[i] == NIL){
      dist[i] = 0;
      q.push(i);
    }
    else
      dist[i] = INF;
  }
  dist[NIL] = INF;
  while(q.size()){
    int nod = q.front();
    q.pop();
    for(auto vec:gr[nod]){
      if(dist[pV[vec]] == INF){
        dist[pV[vec]] = dist[nod] + 1;
        q.push(pV[vec]);
      }
    }
    if(dist[NIL] != INF)
      return true;
  }
  return false;
}
bool dfs_find(int nod){
  if(nod == NIL)
    return true;
  for(auto son:gr[nod]){
    int nxt = pV[son];
    if(dist[nxt] == dist[nod] + 1){
      bool type = dfs_find(nxt);
      if(type == true){
        pU[nod] = son;
        pV[son] = nod;
        return true;
      }
    }
  }
  dist[nod] = INF;
  return false;
}
int main()
{
  ifstream cin("cuplaj.in");
  ofstream cout("cuplaj.out");
  int nrm;
  cin>>nrU>>nrV>>nrm;
  for(int i = 1; i<=nrm; i++){
    int x, y;
    cin>>x>>y;
    gr[x].push_back(y);
  }
  for(int i = 1; i<=nrU; i++)
    pU[i] = NIL;
  for(int i = 1; i<=nrV; i++)
    pV[i] = NIL;
  int match = 0;
  while(bfs_alter()){
    for(int i = 1; i<=nrU; i++){
      if(pU[i] == NIL)
        if(dfs_find(i))
          match++;
    }
  }
  cout<<match<<"\n";
  for(int i = 1; i<=nrU; i++){
    if(pU[i] != NIL)
      cout<<i<<" "<<pU[i]<<"\n";
  }
  return 0;
}