0
$\begingroup$

I am interested in efficient ways of doing certain problem.

I have list of $n$ pairs, where $n$ is usually a few houndred thousands and each pair's element is an integer (let's assume it is integer from $0$ to $10000$) and I am trying to find a sequence such that it start and ends at chosen integer (we can assume it is eg. $0$) and second element of previous pair matches first element of next pair. So as an example, if we have set of pairs $\{(0,1), (1,3), (3, 2) (3,0)\}$ the valid sequence would be eg. $(0,1), (1,3), (3, 0)$. If there is a few answers then I can find arbitrary one. Moreover it is no certain that my list of pairs actually has a solution. If it does not have solution, then the method should return no valid solutions.

I think that maybe some kind of dynamic programming could be useful here, but I don't really have an idea for something better than just checking all the options, which I am almost certain is quite bad. Do you have any interesting insight about this problem?

$\endgroup$
1
$\begingroup$

The integers of your problem form nodes, the pairs form directed edges. Then you can use Tarjan's strongly connected components algorithm to find the groups of nodes that form a cycle.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.