floyd求传递闭包

传递闭包问题，我的理解就是通过一些已知的连边求出点与点之间的关系

设f[i][j]表示i 与 j 是否联通，f[i][j]=f[i][k]&&f[k][j]

时间复杂度O(N^3)

POJ-3660

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 110;
int a[maxn][maxn];
int n,m;
int ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for(int k=1;k<=n;k++)
	   for(int i=1;i<=n;i++)
	      for(int j=1;j<=n;j++)
	          if(a[i][k]&&a[k][j])
	             a[i][j]=1;
	for(int i=1;i<=n;i++)
	{
		int du=0;
		for(int j=1;j<=n;j++)
		   if(a[i][j]||a[j][i])
		      du++;
		if(du==n-1) ans++;
	}
	cout<<ans;
	return 0;
}