POJ-3660-Cow Contest

题目描述：

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.

输入：

  • 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

输出：

Line 1: A single integer representing the number of cows whose ranks can be determined 　

输入示例：

1
2
3
4
5
6
5 5
4 3
4 2
3 2
1 2
2 5

输出示例：

1
2

题目大意：

有N头牛，现在给出M个输赢列表（第一代表赢，第二代表输），并且实力是绝对的（这句话很重要）。要求你确定谁的排名是确定的，输出确定的个数。

思路：

使用传递闭包来确定赢的关系，并通过判断其中一头牛与其他牛是否都有联系（赢了别的牛，或输给了别的牛）。如果与其余N-1条牛都有联系，说明该牛的排名是确定的。

Solution：

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
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
const int MAXN = 200;
const int INF = 0x3f3f3f3f;

int G[MAXN][MAXN];
int N,M;
int main(){
    freopen("in.txt","r",stdin);
    memset(G,0,sizeof(G));
    scanf("%d%d",&N,&M);
    for(int i = 0; i < M; i++){
        int a,b;
        scanf("%d%d",&a,&b);
        //生成a赢b的关系图
        G[a][b] = 1;
    }
    
    for(int k = 1; k <= N; k++)
        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                //B>C，A>B，说明A>C
                if(G[i][k] && G[k][j]) G[i][j] = 1;

    /*
    只有当一个点与其他个点都有联系（或赢或输）,才可以确定该点
    */
    int ans = 0;
    for(int i = 1; i <= N; i++){
        int sum = 0;
        for(int j = 1; j <= N; j++){
        // 又因为该题有唯一的赢输判定，所以与其他各点都有联系可以直接表示为加的和为N-1
        // 否则只能一一判定当前点与其他个点的关系。
            sum = sum + G[i][j] + G[j][i];
        }
        if(sum == N-1) ans++;
    }
    printf("%d\\n",ans);

    return 0;
}