P2341 [USACO03FALL / HAOI2006] Popular Cows G

The testdata for this problem has been fixed.

Every cow dreams of becoming the star of the barn. A cow that is liked by all cows is a star cow. All cows are self-obsessed; each cow always likes itself. The “likes” relation is transitive—if $A$ likes $B$, and $B$ likes $C$, then $A$ also likes $C$. There are $N$ cows in the barn. Given some admiration relationships between cows, please compute how many cows can be stars.

The first line contains two space-separated integers: $N$ and $M$. The next $M$ lines: each line contains two space-separated integers: $A$ and $B$, meaning $A$ likes $B$.

Output a single integer on one line, the number of star cows.

Only cow number $3$ can be a star. Constraints - For $10\%$ of the testdata, $N \le 20$, $M \le 50$. - For $30\%$ of the testdata, $N \le 10^3$, $M \le 2 \times 10^4$. - For $70\%$ of the testdata, $N \le 5 \times 10^3$, $M \le 5 \times 10^4$. - For $100\%$ of the testdata, $1 \le N \le 10^4$, $1 \le M \le 5 \times 10^4$. Translated by ChatGPT 5