Graphical algorithm for matching nodes

Question

Given a directed graph, which algorithm can I use to find a random subset of its edges, so that each node has exactly one incoming and exactly one outgoing edge?

For example, this could be a graph that I give:

And this will be a valid output graph:

This is true because:

• It contains all the nodes in the input graph.
• All its edges are also on the input graph.
• Each node has exactly one edge, leaving it, and one edge will come to it (and this cannot be the same edge, no loops are allowed, each node must connect to at least one other node).

If there is no possible solution that needs to be discovered.

Is there an efficient algorithm to solve this problem?

Thank!

Answer 1

node. .

:

• node , , P1 P2. A D A1, D1 P1 A2, D2 P2. Edge A-D A1-D2, D-A - D1-A2.
• , .
• , .

Answer 2

.

Tarjan .

( , ).