Pagini recente » Cod sursa (job #1893615) | Cod sursa (job #2556650) | Cod sursa (job #109761) | Cod sursa (job #3262595) | Cod sursa (job #2872002)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
bool fost[20011];
int coup[20011];
vector <int> v[10011];
int cuplaj(int k)
{
if(fost[k]==1)
return 0;
fost[k]=1;
for(auto it=v[k].begin();it!=v[k].end();it++)
if(coup[*it]==0)
{
coup[*it]=k;
coup[k]=*it;
return 1;
}
for(auto it=v[k].begin();it!=v[k].end();it++)
if(cuplaj(coup[*it])==1)
{
coup[k]=*it;
coup[*it]=k;
return 1;
}
return 0;
}
bool s[20011];
void solve(int k)
{
for(auto it=v[k].begin();it!=v[k].end();it++)
{
if(s[*it]==0)
{
s[*it]=1;
s[coup[*it]]=0;
solve(coup[*it]);
}
}
}
int n,m,i,x,y,schimb,nr;
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
v[x].push_back(y+n);
}
//x+n->out
//x->in
schimb=1;
while(schimb)
{
schimb=0;
memset(fost,0,sizeof(fost));
for(i=1;i<=n;i++)
if(coup[i]==0)
schimb=schimb+cuplaj(i);
}
for(i=1;i<=n;i++)
if(coup[i]>0)
nr++;
g<<n*2-nr<<'\n';
for(i=1;i<=n;i++)
if(coup[i]!=0)
s[i]=1;
for(i=1;i<=n;i++)
if(coup[i]==0)
solve(i);
for(i=1;i<=n;i++,g<<'\n')
{
if(s[i]==1 && s[i+n]==1)
{
g<<0;
continue;
}
if(s[i+n]==1)
{
g<<1;
continue;
}
if(s[i]==1)
{
g<<2;
continue;
}
g<<3;
}
return 0;
}