·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接:http://poj.org/problem?id=3660
对于每一头牛，能够确切判断它的名次，当且仅当它与其他n-1头牛都能直接判断胜负。对于给定的战胜关系a->b，我们连一条从a到b的边。在生成的图上跑一遍Floyd，就可以判断任意两点是否直接或间接相连了，此时枚举每一个点，如果该点与其它n-1个点都相连（包括正向和反向，即战胜和被战胜），那么该点的名次就是确定的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int n, m;
const int maxn = 101;
bool beat[maxn][maxn];
void floyd() {
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if (beat[i][k] && beat[k][j])
beat[i][j] = 1;
}
int main() {
int a, b, ans = 0;
memset(beat, 0, sizeof(beat));
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
beat[a][b] = 1;
}
floyd();
for(int i = 1; i <= n; i++) {
bool flag = 1;
for(int j = 1; j <= n; j++)
if (!beat[i][j] && !beat[j][i] && i != j) {
flag = 0;
break;
}
if (flag) ans++;
}
printf("%d", ans);
}