Use three colors: white (unvisited), gray (in current path), black (finished). This is a standard DFS technique for detecting cycles. When you reach a gray node, you have found a cycle. The cycle consists of all gray nodes from that point.
When you reach a black node, use its precomputed answer. This is a classic DFS technique for cycle detection in functional graphs. It generalizes to general graphs with slight modifications.