Pagini recente » Cod sursa (job #185345) | Profil CosminaBuruiana | Cod sursa (job #171428) | sim2 | Cod sursa (job #562238)
Cod sursa(job #562238)
#include <fstream>
#include <cstring>
#define nmax 10005
using namespace std;
ifstream fin("cuplaj.in");
ofstream fout("cuplaj.out");
int uz[nmax], st[nmax], dr[nmax];
int n, m, e, nr, sup, a, b;
struct lista
{
int inf;
lista * nod;
} * g[nmax];
void add(int i, int j)
{
lista * p;
p = new lista;
p -> inf = j;
p -> nod = g[i];
g[i] = p;
}
int cuplaj(int nod)
{
lista * p;
if(uz[nod]) return 0;
uz[nod] = 1;
for(p = g[nod]; p; p = p->nod)
if(!dr[p->inf] || cuplaj(dr[p->inf]))
{
st[nod] = p->inf;
dr[p->inf] = nod;
return 1;
}
return 0;
}
int main()
{
int i;
fin >> n >> m >> e;
for(i = 1; i <= e; ++ i)
{
fin >> a >> b;
add(a, b);
}
sup = 1;
while(sup)
{
sup = 0;
memset(uz, 0, sizeof(uz));
for(i = 1; i <= n; ++ i)
if(!st[i] && cuplaj(i))
{
sup = 1;
++ nr;
}
}
fout << nr << "\n";
for(i = 1; i <= n; ++ i)
if(st[i] )
fout << i << " " << st[i] << "\n";
return 0;
}