InputThe input contains multiple test cases.
The first line has one integer,represent the number of test cases.
Each case first contains two integers N and M(N , M <= 500), N is the number of ACMers in HDU team, and M is the number of matchs have been held.The following M lines, each line means a match and it contains two integers A and B, means A wins the match between A and B.And we define that if A wins B, and B wins C, then A wins C.OutputFor each test case, output a integer which represent the max possible number of queries that you can‘t tell lcy.Sample Input
3 3 3 1 2 1 3 2 3 3 2 1 2 2 3 4 2 1 2 3 4
Sample Output
0
0
4
Hint
in the case3, if lcy ask (1 3 or 3 1) (1 4 or 4 1) (2 3 or 3 2) (2 4 or 4 2), then you can‘t tell him who is the winner.
题意：有一场比赛，对于n个选手给出m场比赛的结果，结果有传递性，问有多少对选手不能判断他们之间的胜负关系。
思路 :floyd求解传递闭包
AC代码：
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 #define maxn 766 5 int e[maxn][maxn]; 6 int main(){ 7 int _; 8 cin>>_; 9 while(_--){ 10 int n,m; 11 scanf("%d%d",&n,&m); 12 int x,y; 13 while(m--){ 14 //cin>>x>>y; 15 scanf("%d%d",&x,&y); 16 e[x][y]=1; 17 } 18 for(int k=1;k<=n;k++) 19 for(int i=1;i<=n;i++){ 20 if(!e[i][k]) 21 continue; 22 for(int j=1;j<=n;j++) 23 if(e[i][k]&&e[k][j]) 24 e[i][j]=1; 25 } 26 27 28 int ans=0; 29 for(int i=1;i<=n;i++) 30 for(int j=i+1;j<=n;j++) 31 if(!e[i][j]&&!e[j][i]) 32 ans++; 33 printf("%d\n",ans); 34 for(int i=1;i<=n;i++) 35 for(int j=1;j<=n;j++) 36 e[i][j]=0; 37 } 38 }
原文：https://www.cnblogs.com/pengge666/p/11631966.html