传递闭包裸题
但是本题的Floyd一定要优化,不然会T
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
int T,n,m,dis[505][505],cnt;
int main(){
T=init();
while(T--){
n=init();m=init();
memset(dis,0,sizeof(dis));
cnt=0;
for(int i=1;i<=m;i++){
int u=init(),v=init();
dis[u][v]=1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(dis[i][k]){
for(int j=1;j<=n;j++){
dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]) cnt++;
}
}
cout<<(n*n-n-cnt*2)/2<<endl;
}
return 0;
}