Pagini recente » Cod sursa (job #2898985) | Cod sursa (job #2757366) | Cod sursa (job #573459) | Cod sursa (job #2526833) | Cod sursa (job #533631)
Cod sursa(job #533631)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "cuplaj.in";
const char oname[] = "cuplaj.out";
ifstream fin(iname);
ofstream fout(oname);
int n, m, i, x, y, cuplat, c, e, viz[8900], R[8900], L[8900];
vector<int> Gr[8900];
int pair_up(int nod)
{
if(viz[nod] == 1)
return 0;
viz[nod] = 1;
for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++it)
if(pair_up(R[*it]))
{
L[nod] = *it;
R[*it] = nod;
return 1;
}
for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++it)
if(R[*it] == 0)
{
L[nod] = *it;
R[*it] = nod;
return 1;
}
return 0;
}
int main()
{
fin >> n >> m >> e;
for(i = 1; i <= e; i ++)
{
fin >> x >> y;
Gr[x].push_back(y);
}
cuplat = 1;
while(cuplat)
{
for(i = 1; i <= n; i ++)
viz[i] = 0;
cuplat = 0;
for(i = 1; i <= n; i ++)
if(L[i] == 0)
if(pair_up(i))
++c, cuplat = 1;
}
fout << c << "\n";
for(i = 1; i <= n; i ++)
if(L[i])
fout << i << " " << L[i] << "\n";
return 0;
}