Hi I am getting TLE in the 7th test case. How do I optimize my code? Problem link: http://www.spoj.com/problems/MATCHING/
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
#define in(a) scanf("%d",&a);
#define pb push_back
vector <int> G[50000+5];
bool seen[50000+5];
int matchL[50000+5],matchR[50000+5],A[50000+5];
int n,m;
bool bpm(int u)
{
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(seen[v])
continue;
seen[v]=true;
if(matchR[v]<0 || bpm( matchR[v] ))
{
matchR[v]=u;
matchL[u]=v;
return true;
}
}
return false;
}
int main()
{
int n,m,p;
set<int> row;
set<int> col;
set<int>::iterator it;
int pos=0;
in(n);in(m);in(p);
while(p--)
{
int x,y;
in(x);in(y);
if(row.find(x)==row.end()){
row.insert(x);
A[pos++]=x;
}
G[x].pb(y);
}
/*for(int i=0;i<10;i++)
cout<<A[i]<<" ";
cout<<endl;*/
memset(matchL,-1,sizeof(matchL));
memset(matchR,-1,sizeof(matchR));
m=row.size();
//n=B.size();
int cnt=0;
for(int i=0;i<m;i++)
{
memset(seen,0,sizeof(seen));
if( bpm( A[i] ) )
cnt++;
}
printf("%d\n",cnt);
return 0;
}








It's obiviously that your solution can get TLE. The command "memset(seen,0,sizeof(seen))" is called exactly m times (m<=50000). It's impossible to memset an array of size 50000 for 50000 times in 3s.
You should also notice that, this problem can't be solved by regular max-matching algorithm. You must use Hoftcroft-Karp or Dinitz to solve it.