Pagini recente » Cod sursa (job #623007) | Cod sursa (job #2733801)
#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;
}