Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <cstring>
- #define N 50001
- #define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
- #define FORI(i,V) for(vector <int>::iterator i=(V).begin();i!=(V).end();++i)
- using namespace std;
- const char iname[]="falkland.in";
- const char oname[]="falkland.out";
- vector <int> G[N];
- int l[N],r[N],u[N];
- int pairup(const int n)
- {
- if(u[n])
- return 0;
- u[n]=1;
- FORI(i,G[n])
- if(!r[*i])
- {
- l[n]=*i;
- r[*i]=n;
- return 1;
- }
- FORI(i,G[n])
- if (pairup(r[*i]))
- {
- l[n]=*i;
- r[*i]=n;
- return 1;
- }
- return 0;
- }
- int main(void)
- {
- freopen(iname,"r",stdin);
- int n,m,k;
- scanf("%d %d %d",&n,&m,&k);
- int x,y;
- while(k--)
- scanf("%d %d",&x,&y),G[x].push_back(y);
- for(int change=1;change;)
- {
- change=0;
- memset(u,0,sizeof(u));
- FOR (i,1,n)
- if(!l[i])
- change|=pairup(i);
- }
- int r=0;
- FOR(i,1,n)
- r+=(l[i]>0);
- freopen(oname,"w",stdout);
- printf("%d\n",r);
- FOR(i,1,n)
- if(l[i]>0)
- printf("%d %d\n",i,l[i]);
- return 0;
- }
Add Comment
Please, Sign In to add comment