Cow Contest
InterviewTime limit1sMemory limit128 MB
Given the winners of head-to-head matches, count how many cows have a skill rank that is fully forced by the results.
- Level
Medium5 of 10
- Topics
- Graph, DFS, Shortest path, Dynamic programming
- Solved
- No attempts yet
Problem
() cows, conveniently numbered through , are competing in a programming contest. As everyone knows, some cows code better than others. Each cow has a fixed skill rating that is unique among the competitors.
The contest is run as a series of head-to-head rounds, each between two cows. If cow has a higher skill level than cow (, , ), then cow always beats cow .
Farmer John wants to rank the cows by skill. Given the results of () two-cow rounds, determine how many cows have a rank that can be precisely determined from those results. The round results are guaranteed to be free of contradictions.
Input
- Line 1: Two space-separated integers, and .
- Lines through : Each line contains two space-separated integers describing one round, and , where the first integer is the winner.
Output
- Line 1: A single integer, the number of cows whose rank can be determined.