modification of topological sorting to support cycle I'm countering a problem similar to topological sorting:
I need to give a sequence of nodes for the directed graph so that all edges can be matched in the sequence('match' means that for edge a->b, there exists node a in the left of node b). Note that the sequence allows repeated nodes.
For example,for graph:
a->b,b->c,c->d,c->a

The sequence a b c a d is one of the corrected answers.
Does this problem is an exactly well-known problem?
 A: Note that the sequence a b c d e f g f e d c b a is a solution for any directed graph with vertex set $\{a,b,c,d,e,f,g\}$ (and we can solve the problem similarly for any number of nodes). The interesting question is to find the shortest possible solution, which means minimizing the number of nodes that appear twice.
For every directed cycle in the graph, at least one node on the cycle must appear twice, or else one of its edges will not be matched in the sequence. So the nodes that appear twice must be a feedback vertex set: a set that includes one vertex of every cycle. Conversely, if $S$ is a feedback vertex set, there is a solution in which only the vertices in $S$ appear twice:

*

*Begin the sequence by listing all vertices in $S$, in an arbitrary order.

*Then, list the vertices not in $S$, in a topological order (without $S$, there are no cycles, so the remaining vertices can be topologically sorted).

*Then, list all vertices in $S$ again, in reverse of the order used in step 1.

So the problem is equivalent to finding the smallest feedback vertex set...
... which, unfortunately, is an NP-complete problem. The Wikipedia article linked to above contains more details.
