/*pku 2890 matrix multiplication */
//传递闭包
//图形算法
#include<stdio.h>
#include<string.h>
#define N 1050
int map[N][100],len[N];
int pre[N],tc[N][N];
int n,m;

void tcdfs(int u,int p)
{
	int ii;
	int temp;
	
	for(ii=1;ii<=len[u];ii++)
	{
		temp=map[u][ii];
		if(pre[temp]) continue;
		pre[temp]=1;
		tc[p][temp]=1;
		tcdfs(temp,p);	
	}
}

void dagtc()
{
	int ii,jj;
	int num;
	
	memset(tc,0,sizeof(tc));
	for(ii=1;ii<=n;ii++)
	{
		 memset(pre,0,sizeof(pre));
		 pre[ii]=1;
		 tcdfs(ii,ii);	 
	}

	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)
	{
		memset(len,0,sizeof(len));
		for(ii=1;ii<=m;ii++)
		{
			scanf("%d %d",&a,&b);
			a++,b++;
			len[a]++;
			map[a][len[a]]=b;
		}
		
		dagtc();
	}
	return 1;
}
/*
3 4
1 2
2 1
0 1
0 2
5 2
1 2
2 3
*/
贴代码是挫事，但还是做一下

• 贴上去试了一下，AC了 (1156) oeym 2006-07-31 22:28:48
  • Re:你真挫，明知道我贴错了，还回贴 (0) xiangsanzi 2006-07-31 22:29:23
    • 得確是一個很好的發表代碼的方式 (15) sza 2006-10-19 14:08:44
• 贴错了，是这个代码，谁帮忙看一下 (1156) xiangsanzi 2006-07-31 22:29:54
  • Re:代码见内 (1014) xiangsanzi 2006-07-31 22:30:54
    • 没有进行传递闭包的运算 (0) sasnzy 2006-08-26 20:58:46