题意:N 个人,M 场比赛,每场比赛第一个数是胜者,胜负关系具有传递性。问这些人不能确定胜负关系有几对。POJ3360 与此题题意相同,只不过改成了求能确定排名的人数(一个人与其他所有人的胜负关系都是确定的情况下就能确定排名)。
给出 HDU1704 的 AC 代码,POJ3360 在此代码稍微修改下即可。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
int pic[600][600];
int main(){
//freopen("a.txt", "r", stdin);
int t;
cin >> t;
while(t--){
memset(pic, 0, sizeof(pic));
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
pic[i][i] = 1;
while(m--){
int a, b;
scanf("%d %d", &a, &b);
pic[a][b] = 1;
}
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
if(pic[i][k]){
for(int j = 1; j <= n; j++){
if(pic[k][j])
pic[i][j] = 1;
}
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = i+1; j<= n; j++){
if(!pic[i][j] && !pic[j][i])
ans++;
}
cout << ans <<endl;
}
return 0;
}