Pagini recente » Cod sursa (job #2885998) | Cod sursa (job #1381190) | Cod sursa (job #836830) | Cod sursa (job #2335377) | Cod sursa (job #2376265)
#include <bits/stdc++.h>
#define N 10005
using namespace std;
ifstream fin("cuplaj.in") ;
ofstream fout("cuplaj.out") ;
int a , b , e ,sol;
int lft[N] ,rght[N] ;
bool viz[N] ;
vector<int> graf[N] ;
void citire()
{
int i , x , y ;
fin >> a >> b >> e ;
for ( i = 1 ; i <= e ; i++ )
{
fin >> x >> y ;
graf[x].push_back(y) ;
}
}
bool cuplaj(int nod)
{
if ( viz[nod] == true )
return false;
viz[nod] = true ;
for ( auto vec : graf[nod] )
{
if ( rght[vec] == 0 )
{
lft[nod] = vec ;
rght[vec] = nod ;
sol++ ;
return true ;
}
}
for ( auto vec : graf[nod] )
{
if ( cuplaj(rght[vec]) == true )
{
lft[nod] = vec ;
rght[vec] = nod ;
return true ;
}
}
return false;
}
int main()
{
int i ;
bool ok = false;
citire() ;
do
{
ok = false;
for ( i = 1 ; i <= a ; i++ )
viz[i] = true ;
for ( i = 1 ; i <= a ; i++ )
if ( lft[i] == 0 )
ok = ok|cuplaj(i) ;
} while ( ok == true ) ;
fout << sol << '\n' ;
for ( i = 1 ; i <= a ; i++ )
if ( lft[i] )
fout << i << " " << lft[i] << '\n' ;
}