Cod sursa(job #1630192)
Utilizator | Horea Stefan AeroH | Data | 4 martie 2016 23:07:48 |
---|---|---|---|
Problema | Cuplaj maxim in graf bipartit | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <bits/stdc++.h>
#define N 10000
using namespace std;
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");
int n,m,k,i,C,R[N],L[N],x,y;
vector<int> v[N];
bitset<N> T;
int P(int n)
{
if (T[n])return 0;T[n]=1;
for (auto j:v[n])if (!L[j]||P(L[j]))
return L[j]=n,R[n]=j;
return 0;
}
int main()
{
f>>n>>m>>k;
for (i=1;i<=k;++i)
f>>x>>y,v[x].push_back(y);
for(i=1;i<=n;++i)
if (!R[i]&&P(i))++C,T=0;
g<<C<<'\n';
for (i=1;i<=n;++i)
if (R[i])g<<i<<" "<<R[i]<<'\n';
return 0;
}