Detecting cycles in a directed graph without using mutable sets of nodes
An easy way to detect a cycle is through the implementation of a disjoint set structure, sometimes called a Union-Find structure. 

You start with a source node and attempt to add a node to that set.  If your   Find() call for the source node and the other node returns the same root node, then a cycle world result if the nodes are unioned.

UPDATE:

You could implement a topological sort, arranging the nodes with edges going from left to right. A topological sort can only be completed successfully if and only if the graph is a Directed Acyclic Graph. So, if the algorithm detects any cycles, it will stop.

The runtime is O(|V| + |E|), which is better than DFS, in the case that repetition occurs during traversal.

Topological Sorting