title: Graphing Algorithm To Match Nodes
body: <p>Given a directed graph, what is an algorithm I can use to find a random subset of its edges so that every node has exactly one incoming and exactly one outgoing edge?</p>
  
  <p>For example, this could be the graph I am given:</p>
  
  <p><img src="https://i.stack.imgur.com/U7pBr.png" alt="Starting input graph"></p>
  
  <p>And this would be a valid output graph:</p>
  
  <p><img src="https://i.stack.imgur.com/BSpc8.png" alt="A valid output graph"></p>
  
  <p>This is valid because:</p>
  
  <ul>
  <li>It contains all the nodes on the input graph</li>
  <li>All its edges are also on the input graph</li>
  <li>Every node has exactly one edge leaving it and one edge coming to it (and that can't be the same edge, no loops are allowed, every node has to connect to at least one other node).</li>
  </ul>
  
  <p>If there is no possible solution that should be detected.</p>
  
  <p>Is there an efficient algorithm to solve this?</p>
  
  <p>Thanks!</p>