Author(s) François Aubry
Deadline No deadline
Submission limit No limitation

Sign in

Graphs - Problem: Dominos


Adapted from: UVa 11504

Dominoes are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line.

However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominoes falling again.

Your task is to determine, given the layout of some domino tiles, the minimum number of dominoes that must be knocked down by hand in order for all of the dominoes to fall.


  • One line with two integers \(n\) and \(m\) giving the number of dominoes and the number pairs of dominoes that make each other fall.
  • \(m\) lines each with two integers \(i\) and \(j\) giving that if \(i\) falls then domino \(j\) also falls.

Note that in this problem a domino may cause any number of other dominoes to fall.


  • \(1 \leq n \leq 100000\)
  • \(0 \leq m \leq 1000000\)
  • \(0 \leq i, j < n\)


  • One line with the minimum number of dominoes that we need to push in order to make all dominoes fall.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2

Max file size: 1.0 MiB
Allowed extensions: .java, .cpp, .py