Code to calculate minimum number of pushes required to put the whole dominoes set down
Alternate algorithm
I would suggest the following:

After reading the list of domino dependencies, you should be able to compute a set of &quot;root&quot; dominos.  A &quot;root&quot; domino is simply a domino that is not pushed by any other domino.
Each root domino must be pushed, since there is no other domino to push it.  So for each root domino, push it, and do a dfs to mark all dominos knocked down by it.
After step #2, there may be dominos left standing.  These dominos must either be part of a cycle, or hanging off of a cycle.
For each remaining domino, do a dfs on it, looking for a cycle.
If the domino did not cycle, then do not increment the push count, but mark all the dominos in the dfs as knocked over.  This was a domino hanging off a cycle, and you know that this domino's parent(s) will eventually get knocked over by some other push.
If the domino did cycle, then keep a list of each domino that was part of its cycle (note that there could be more than one cycle through the same domino).  After doing the dfs and marking all dominos as knocked down, go through the list of dominos that were part of its cycle.  If any of them have a parent that is still standing, then do not increment the push count.  The reason is that the still standing parent will get pushed by some other domino, and it will knock down this whole cycle.  In other words, if a cycle of dominos has an external parent, then it can be ignored because the push from another cycle that triggers the external parent will knock down this cycle.

I haven't actually written a program to test this algorithm, so there could be a flaw in my logic dealing with cycles.  But I think it should work, and it should be fast because you never process a node more than once.