Faulty Robot

This problem asks us to find the set of sink nodes while traversing a graphs by a set of edges with a caveat that we may traverse a second set of "fault" edges, but only one such edge may ever be traversed.

This is a standard state explosion problem. Without the "fault" edges, we could simply BFS and check which nodes don't allow us to progress further. With the "fault" edges, we add a second variable to our state to track whether we've taken some fault edge already. If we have not, we BFS along any edge, fault or regular. If we have, we may only traverse along regular edges.