Floyed过不了
查看原帖
Floyed过不了
285617
黑影洞人楼主2021/10/1 21:44
#include<cstdio>
#include<algorithm>
#define N 10005
using namespace std;
int dis[N][N],n,m,ans; 
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dis[i][j]=0x7fffff;
		}
		dis[i][i]=0;
	}
	for(int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		dis[b][a]=1;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(dis[i][k]+dis[k][j]<dis[i][j]){
					dis[i][j]=dis[i][k]+dis[k][j];
				} 
			}
		}
	}
	for(int i=1;i<=n;i++){
		bool flg=1;
		for(int j=1;j<=n;j++){
			//printf("%d %d %d\n",i,j,dis[i][j]);
			if(i==j)continue;
			if(dis[i][j]>=0x7fffff){
				flg=0;break;
			}
		}
		if(flg)ans++;
	}
	printf("%d",ans);
	return 0;
}



2021/10/1 21:44
加载中...