Hust oj 1018 Cow Contest(floyd传递闭包）_综合

Cow Contest

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 261(103 users)

Total Accepted: 120(96 users)

Rating:

Special Judge: No

Description

N (1 ≤ N ≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B), then cow A will always beat cow B.
Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

For each test case:
* Line 1: Two space-separated integers: N and M
 * Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
Process to the end of file.

Output

For each test case:
* Line 1: A single integer representing the number of cows whose ranks can be determined

Sample Input

Sample Output

2

floyd传递闭包来计算名次

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn = 105;
const int Inf = 0x3f3f3f;
int n,m;
int map[maxn][maxn];void init()
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){map[i][j] = 0;}}
}void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(map[i][k] && map[k][j]) map[i][j] = 1;}}}
}
int  main()
{while(~scanf("%d%d",&n,&m)){init();for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);map[x][y] = 1;}floyd();int sum = 0;for(int i=1;i<=n;i++){int ans = 0;for(int j=1;j<=n;j++){if(i == j) continue;if(map[i][j] || map[j][i])ans++;}if(ans == n - 1)sum++;}cout<<sum<<endl;}
}