Cow Contest (Талдау)

Let us define a Boolean matrix $g$. For each pair of cows $a$ and $b$, set g[a][b] = true if cow $a$ defeats cow $b$. In other words, we draw a directed edge from $a$ to $b$. Since the results of the rounds are consistent, the resulting graph is acyclic.

The rank of cow $i$ can be determined if, for every other cow $j$, we know which of them is stronger: either cow $i$ can defeat cow $j$ (possibly through several intermediate cows), or cow $j$ can defeat cow $i$. In other words, in the transitive closure of the graph, for every pair $i$ and $j$, at least one of the following conditions must hold: g[i][j] = true or g[j][i] = true.

Both g[i][j] and g[j][i] cannot be $true$ at the same time, because that would imply a contradiction in the competition results.

Example

In the example above, the ranks can be determined unambiguously only for cows $2$ and $5$.

Cow $2$ Cow $5$ but loses to all the other cows. Cow $5$ loses to all the other cows.

For cow $1$ it is unknown whether she can beat cows $3$ and $4$. Similarly, for cows $3$ and $4$ it is unknown whether they can beat cow $1$. Therefore, the exact ranks of these cows cannot be determined.

Algorithm implementation

Define a boolean matrix $g$.

bool g[101][101];

Read the input data.

scanf("%d %d", &n, &m);

Assume that every cow beats itself.

for (i = 1; i <= n; i++) g[i][i] = 1;

Read the input data and construct the directed graph. If cow $a$ beats cow $b$, add a directed edge from $a$ to $b$.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = 1;
}

Compute the transitive closure of the graph. If there is a path from vertex $i$ to vertex $j$, set g[i][j] = true.

for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
  if (g[i][k] && g[k][j]) g[i][j] = true;

Use the variable $res$ to keep track of the number of cows whose ranks can be determined unambiguously.

res = 0;

In the loop, check each cow one by one and determine whether its rank can be determined unambiguously.

for (i = 1; i <= n; i++)
{

Check whether the rank of cow $i$ can be determined. To do this, we iterate over all cows $j$. If, for some cow, both conditions hold: g[i][j] = false and g[j][i] = false, then it is impossible to determine which of the two cows is stronger. Therefore, the exact rank of cow $i$ cannot be determined.

  bool good = true;
  for (j = 1; j <= n; j++)
    if (g[i][j] == false && g[j][i] == false)
    {
      good = false;
     break;
    }

If, after checking all cows, the value of $good$ remains $true$, then the position of cow $i$ relative to every other cow is known. Therefore, its rank can be determined unambiguously.

  if (good) res++;
}

Print the answer.

printf("%d\n", res);