Pagini recente » Cod sursa (job #1051519) | Cod sursa (job #725979) | Cod sursa (job #1126721) | Cod sursa (job #1123044) | Cod sursa (job #222590)
Cod sursa(job #222590)
#include <cstdio>
#include <string>
#define N 8201
struct nod { int x; nod *n;};
nod *a[N];
int n, m;
bool use[N];
bool use1[N];
int l[N], r[N], sl[N], sr[N];
inline void add(int x, int y)
{
nod *p=new nod ;
p->x=y;
p->n=a[x];
a[x]=p;
}
void read()
{
freopen("felinare.in","r",stdin);
scanf("%d %d\n", &n,&m);
int p,q;
while(m--)
{
scanf("%d %d\n", &p, &q);
add(p,q);
}
}
inline bool pairup(int n)
{
if(use[n]) return 0;
use[n]=1;
for(nod *i=a[n]; i; i=i->n)
if(!l[i->x])
{
l[i->x]=n;
r[n]=i->x;
sl[n]=1;
return 1;
}
for(nod *i=a[n]; i; i=i->n)
if(pairup(l[i->x]))
{
l[i->x]=n;
r[n]=i->x;
sl[n]=1;
return 1;
}
return 0;
}
void suport(int n)
{
for(nod *i=a[n]; i ; i=i->n)
if(!sr[i->x])
{
sr[i->x]=1;
sl[l[i->x]]=0;
suport(l[i->x]);
}
}
void hopcroft_karp()
{
int ok=1,i,flow=0;
while(ok)
{
ok=0;;
memset(use, 0, sizeof(use));
for(i=1;i<=n;++i)
if(!r[i])
if(pairup(i)) ++flow,ok=1;
}
freopen("felinare.out","w",stdout);
printf("%d\n", 2*n-flow);
//for(i=1;i<=n;++i) fprintf(stderr,"%d ", use[i]);
//fprintf(stderr,"\n");
// for(i=1;i<=n;++i)
//if(l[i]) sl[i]=1;
for(i=1;i<=n;++i)
if(!l[i]) suport(i);
// for(i=1;i<=n;++i)
// if(r[i] == 1) sr[i]=1;
for(i=1;i<=n;++i)
printf("%d\n", 1-(sl[i])+2*(1-sr[i]));
}
int main()
{
read();
hopcroft_karp();
return 0;
}