Pagini recente » Cod sursa (job #3038410) | Cod sursa (job #1592135) | Cod sursa (job #2309793) | Cod sursa (job #47399) | Cod sursa (job #1360783)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10010;
ifstream F("cuplaj.in");
ofstream G("cuplaj.out");
int n,m,e,p1[N],p2[N],mk[N];
vector<int> v[N];
int can(int y)
{
if ( mk[ p2[y] ] ) return 0;
if ( p2[y] == 0 ) return 1;
int x = p2[y];
mk[x] = 1;
for (int i=0;i<int(v[x].size());++i)
{
int y2 = v[x][i];
if ( y2 != y )
if ( can(y2) )
{
p1[x] = y2;
p2[y2] = x;
return 1;
}
}
return 0;
}
int main()
{
F>>n>>m>>e;
for (int i=1,x,y;i<=e;++i)
{
F>>x>>y;
v[x].push_back(y);
}
int co = 0;
for (int x=1;x<=n;++x)
{
memset(mk,0,sizeof(mk));
for (int j=0;j<int(v[x].size());++j)
{
int y = v[x][j];
if ( can(y) )
{
p1[x] = y;
p2[y] = x;
++co;
break;
}
}
}
G<<co<<'\n';
for (int i=1;i<=n;++i)
if ( p1[i] )
G<<i<<' '<<p1[i]<<'\n';
}