# uva: Cow Contest ( Floyd Warshall – Transitive Closure)

October 5, 2014 Leave a comment

**Problem **:

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**

The input contains multiple test cases, until the end of file. Each test case is given in the following order:

- 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

**Output**

For each test case, output in a single line, a single integer representing the number of cows whose ranks can be determined.

**Solution analysis**:

- It is problem of Transitive Closure
- It can be solved using modified Floyd Warshall Transitive Closure algroritm

** C++ Solution:**

#include <stdio.h> #define NMAX 100 int beating[NMAX+1][NMAX+1]; int main() { int m,n,i,j,k,result; while(EOF != scanf("%d %d", &n, &m)) { for(i=0; i < n; i++) { for(j=0; j < n; j++) { beating[i][j] = 0; } beating[i][i] = 1; } while(m--) { scanf("%d %d",&i,&j); beating[--i][--j] = 1; } for(k=0; k < n; k++) for(i=0; i< n; i++) for(j=0; j < n; j++) { if( beating[i][k] && beating[k][j] ) { beating[i][j] = 1; } } result = 0; for(i=0;i < n ; i++) { int nReachable=0; for(j=0; j < n; j++) { nReachable+= beating[i][j] + beating[j][i]; } if(nReachable == n+1 ) result++; } printf("%d\n", result); } return 0; }

**Sample Input**

5 5

4 3

4 2

3 2

1 2

2 5

**Sample Output**

2