hdu 1704 rank 传递闭包

还以为是强连通。。

借用floyd思想，求闭包

#include<cstdio> #include<cstring> #include<vector> #include<stack> using namespace std; const int maxn = 505; int g[maxn][maxn]; int main() { int t,n,m,u,v,ans; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); g[u][v] = 1;//u到v有一条有向边 } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(g[j][i]) for(int k=1;k<=n;k++) if(g[i][k])g[j][k]=1; ans=0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!g[i][j]&&!g[j][i]) ans++; printf("%d\n",ans); } }