2362366_tle.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 36 行

#include <stdio.h>
#include <string.h>
int m, n;
int map[1001][1001];

int warshall()
{
	int i, j, m, t = 0;

	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
			if(map[j][i])
				for(m = 0; m < n; m++)
					if(map[i][m])
						map[j][m]=1;
	}
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			t+=map[i][j];
	return t;
}

int main()
{
	int i;
	int a, b;

	scanf("%d%d",&n,&m);
	memset(map,0,sizeof(map));
	for(i = 0; i < m; i++)
		scanf("%d%d",&a,&b),map[a-1][b-1] = 1;
	printf("%d\n",n*(n-1)/2-warshall());
	return 1;
}