#include<stdio.h>
#include<string.h>
#define N 2050
int map[N][N];
int pre[N],tc[N][N];
int n,m,cnt;

void tcdfsr(int v)
{
	int u,ii;
	pre[v]=++cnt;
	for(u=1;u<=n;u++)
		if(map[v][u])
		{
			tc[v][u]=1;
			if(pre[u]>pre[v]) continue;				
			if(pre[u]==-1) tcdfsr(u);				
			for(ii=1;ii<=n;ii++)
				if(tc[u][ii]) tc[v][ii]=1;					
		}	
}

void dagtc()
{
	int v,num;
	int ii,jj;
	memset(pre,0xff,sizeof(pre));
	memset(tc,0,sizeof(tc));
	cnt=0;
	for(v=1;v<=n;v++)
		if(pre[v]==-1) tcdfsr(v);		
			
	for(ii=1,num=0;ii<=n;ii++)
		for(jj=1;jj<=n;jj++)
		{
			if(ii==jj) tc[ii][ii]=1;
			if(tc[ii][jj]) num++;		
		}
			
	printf("%d\n",num);	
}

int main()
{
	int ii;
	int a,b,temp;
	while(scanf("%d %d",&n,&m)!=EOF&&(m+n))
	{
		memset(map,0,sizeof(map));
		//for(ii=1;ii<=n;ii++) map[ii][ii]=1;
		for(ii=1;ii<=m;ii++)
		{
			scanf("%d %d",&a,&b);
			a++,b++;
			map[a][b]=1;
		}

		dagtc();
	}
	return 1;
}
/*
3 4
1 2
2 1
0 1
0 2
5 2
1 2
2 3
*/

• 没有进行传递闭包的运算 (0) sasnzy 2006-08-26 20:58:46