Pagini recente » Cod sursa (job #876153) | Cod sursa (job #793405) | Cod sursa (job #1627112) | Cod sursa (job #482111) | Cod sursa (job #281225)
Cod sursa(job #281225)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10001
FILE *f=fopen("cuplaj.in","r");
FILE *out=fopen("cuplaj.out","w");
int *g[N];
int s[N],d[N],v[N],n,m,cnt;
int pair(int o){
if(v[o]==1) return 0;
v[o]=1;
int x;
for(x=1;x<=g[o][0];x++){
if(!d[g[o][x]]){
s[o]=g[o][x];
d[g[o][x]]=o;
return 1;
}
}
for(x=1;x<=g[o][0];x++) {
if(pair(d[g[o][x]])){
s[o]=g[o][x];
d[g[o][x]]=o;
return 1;
}
}
return 0;
}
void date(){
int x,y,i;
fscanf(f,"%d%d%d",&n,&m,&cnt);
for(i=1;i<=n;i++){ g[i]=(int*)realloc(g[x],sizeof(int));g[i][0]=0;}
for(; cnt-- ; ){
fscanf(f,"%d%d",&x,&y);
g[x][0]++;
g[x]=(int*)realloc(g[x],(g[x][0]+1)*sizeof(int));
g[x][g[x][0]]=y;
}
}
int main(){
date();
int stare;int i,nr=0;
for(stare=1; stare ; ){
memset(v,0,sizeof(v));
stare=0;
for(i=1;i<=n;i++)if(!s[i]) stare |= pair(i);
}
for(i=1;i<=n;i++) if(s[i]>0) nr++;
fprintf(out,"%d\n",nr);
for(i=1;i<=n;i++) if(s[i]>0) fprintf(out,"%d %d\n",i,s[i]);
return 0;
}