1778.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 

#include"iostream.h"
#include"algorithm"
#include"memory.h"
using namespace std;
const long nsize=100000+10;

long begin[nsize],end[nsize],du[nsize];
_int64 d[100000+10];

long n,m,answer,t,N[2];

void init()
{long i,a,b;
		n=N[0]+N[1];
		for(i=0;i<m;i++){cin>>b>>a;if((a<=N[0]&&b<=N[0])||(a>N[0]&&b>N[0])){m--;i--;continue;}
						d[i]=(_int64)a*(n+1)+b;}

	sort(&d[0],&d[m]);
memset(begin,0,(n+1)*sizeof(long));
memset(end,0,(n+1)*sizeof(long));

begin[d[0]/(n+1)]=0;

for(i=1;i<m;i++)
if(d[i]/(n+1)!=d[i-1]/(n+1))
	{end[d[i-1]/(n+1)]=i;
	begin[d[i]/(n+1)]=i;
	}
end[d[i-1]/(n+1)]=i;



}

long q[2][nsize],s[2],h[2];

void first()
{long i;


memset(du,0,(n+1)*sizeof(long));	
for(i=0;i<m;i++)du[d[i]%(n+1)]++;
s[0]=0;s[1]=0;
for(i=1;i<=n;i++)
if(du[i]==0){if(i<=N[0])q[0][s[0]++]=i;
			else q[1][s[1]++]=i;
			}
h[0]=h[1]=0;
}

void doit(int x)
{long i,j,k;
do
{x=!x;
for(i=h[x];i<s[x];i++)
{for(j=begin[q[x][i]];j<end[q[x][i]];j++)
	{k=d[j]%(n+1);
	du[k]--;
	if(du[k]==0){if(k<=N[0])q[0][s[0]++]=k;
				else q[1][s[1]++]=k;
				}
	}
}
h[x]=s[x];
t++;

}while(h[0]!=s[0]||h[1]!=s[1]);

}

int main()
{
while(1)
{cin>>N[0]>>N[1]>>m;
if(N[0]==0)break;	
init();
t=0;
first();
t=0;
doit(0);
answer=t;

t=0;
first();
doit(1);
if(t<answer)answer=t;
cout<<answer+1<<endl;
}
return 0;
}