Hello,

I am trying to work on a problem from acm.sgu and was wondering if I could ask for guidance in the right direction. The problem statement is here: http://acm.sgu.ru/problem.php?contest=0&problem=101

The way I conceptualize it right now is that it is a DFS problem that can be solved similarly to how N-queens is solved. Is this correct?

For the example input we have: (1)<1,2> (2)<2,4> (3)<2,4> (4)<6,4> (5)<2,1>

A tree or graph of sorts would need to be constructed and traversed like the following:

So that I have an easier time modeling the process/structure in ASCII, let the node (k)*<i,j> represent both the pair (k)<i,j> and the reverse (k)<j,i>

(1)*<1,2> ... (other combinations e.g (2)*,(3)*,etc.)
                              /        \         /        \
                        (2)*<2,4>     (3)*<2,4>  (4)*<6,4>   (5)*<2,1>
                  /    /       \            ..............
         (3)*<2,4>  (4)*<6,4>  (5)*<2,1>
       /    \             ......
 (4)*<6,4> (5)*<2,1>
      .......

Ofcourse with the * notation at each node, the reverse pair would need to be searched as well. I believe DFS can be used here to fine the correct sequence that matches the constraints given by the problem set. Something about this bugs me, though. Because I've never done any graph or tree problems, I don't understand whether I need to precompute a proper graph/tree to fit this problem or if new nodes at the next level down are to be created, checked, searched further or backtracked depending on whether they meet the constraints.

Is this the correct idea of DFS for this problem? If it is, is the tree/graph to be precomputed and then searched, or searched while being created dynamically depending on constraints. If not, could you lend advice on the correct approach for this sort of problem? As a bonus perhaps some sort of reference to follow for representing graphs/trees properly in this sort of situation with C++?

I only have a formal understanding of DFS, so my idea could very likely be wrong. Because I might have a bit of a conceptualization issue here, is it best for me to just read the chapter on graph data structures in CLRS first (I intend to eventually do this, but only if I have to). Again I'm sorry for the bad ASCII job but I figured it was worth sharing to show that I've thought about the problem before asking for advice, though.

Thank you for reading.