title: What's the most efficient way to identify all nodes that are members of a cycle in a directed graph?
body: <p>I have a directed multigraph with no self-loops:</p>
  
  <p><a href="https://i.stack.imgur.com/TTjEa.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/TTjEa.jpg" alt="Multigraph"></a></p>
  
  <p>What's the most efficient way to mark nodes 1, 2 and 3 as being members of a cycle?</p>
  
  <p>My first thought would be to</p>
  
  <ol>
  <li>Perform a depth-first search starting from an arbitrary node</li>
  <li>Push all nodes I've seen in a given branch into a "seen" array. Also, mark each node as "checked".</li>
  <li>For each new node, check if any of its children are in the seen array</li>
  <li>If it is, mark each node in the array between the seen node and its previous occurrence as seen</li>
  <li>While traveling down the DFS, make sure to skip any children who have been seen</li>
  <li>Repeat 1-5 with the next node that hasn't been marked as "checked" yet (since I may have disconnected regions of the graph)</li>
  </ol>
  
  <p>This seems like it might work, but wonder if it's the most efficient way, give that I've got to maintain an array of "seen" nodes, and, since this has to be called recursively, I think I may be doing a lot of array modification (e.g. at one point in my algorithm I'll have [0,1,2,3,1] and another point I'll have [0,1,2,3,4], for the graph above, so it's not just "build once"). I also have to go through the list an additional time at the start to removed the "checked" mark that may have been left over from a previous test.</p>