Key insight: there's no need to eagerly construct the adjacency list. In fact, there's no need to ever construct the adjacency list; you just need a way to find the next nodes. With this insight, we can construct an efficient version of the search.
Lazy edges
For any given node, finding indices i+1 and i-1 is trivial. Finding nodes that have the same value merely requires a lookup in the sets datastructure you've already created.
The rest of your breadth first search still applies equally; you mark off nodes you've already seen to make sure you don't revisit them.
Grouped values
Note that there's really no reason to return to a value once you've left it. Any path that reaches an X-valued index can reach any other X-valued index on the next step. That means your maximum path is 19 (each value can occur at most twice for a 20 nodes i.e. 19 edges along the path).
However, it it also means you don't want the following to occur:
- you're at index K with value X, and iterate over all other indices with value X, marking them as visited, and adding them to the queue
- you eventually reach each one of those X-valued indices in the queue, and iterate over everything it can reach, i.e. all those other X's - even though they've all been visited, and you already know you're not going to add them to the queue.
So you're doing quadratic work (each instance of a value iterates over each instance of the same value) and it's obviously pointless to boot. Once you process an X-valued index and thus visit all other X's, you know you'll never need to follow an X->X edge again. Easy fix? Just empty the list of indices by that value once you've processed one.
This new algorithm is linear time:
- reading the input is linear
- building
sets is linear (each index is inserted once)
- each index can be "processed" (added to the queue) at most once, so that's linear.
- each index can be "visited" (checking the visited array) at most three times: once by i-1, once by 1+1, and once by some other identically valued index.
If you really want, you can possibly shave off a bit of the constant factor here. After all, the final path will pass through each value once (and when it does, touching one or two indexes for that value). You can therefore construct a much, much smaller graph of how values can reach each other; solving that for the shortest paths is essentially free (at most 10 nodes, after all), and a shortest path through the indexes must be the shortest path through the values (proof left to reader, but note that any shortcut via i+1/i-1 costs at least a step, but can never win more than a step). Then, when you solve the bigger graph of indices, you don't need to bother taking any steps that conflict with what you already know of the solution; i.e. don't enqueue any indices that have a value other than your own or the "next" value along any shortest path in the value graph. (In essence, this optimization is A*).
Similarly, you could segment your queue by value and distance, and skip processing the rest of the current value with greater distance once you've found a way to the next.
Such trickery is almost certainly not worth it, but hey, it's possible :-).
Coding Style: I'd suggest naming your variables after what they represent. Your code is a little hard to follow because it contains things like sets (of what? why? - oh it's a way to lookup indices having a value), and a queue q (again, what's this mean? oh it's the reachable set in order of distance). Give meaningful concepts (that you repeat in the code) like adj[dq][i] a name. It's the neighbor you're going to visit. This algorithm is so simple, it's eventually clear, but there's no reason it shouldn't be clear right away.
TL;DR
- Don't precompute edges, instead compute reachability when needed.
- Empty the set of indices you use to compute value-to-value reachability after using it once to avoid quadratic behavior.
- The result is O(N).
Best Answer
I think you should start with the data types that the language has built in like arrays and pointers, and when your students comprehend those, move on to classes and OO, then the STL.
The reason is that you can teach people to understand arrays without understanding much else besides variables and the underlying computer architecture, but you can't teach them to understand
vectorwithout teaching them classes first. If you use the STL from the get go, your students will have to just live with not having a clue about howvectorworks exactly. And then when you get to that point, they won't have a good enough grasp of pointers and arrays and things that you get from doing stuff like writing your own vector class, writing your own linked list class, etc. that will be necessary to appreciate and exploit its features. It annoys me when students say "what's that?" and teachers say "just ignore it, you'll learn it later."And as Demian pointed out in the comments, deciphering the relatively cryptic messages you get from template errors is significantly harder than understanding the errors you may get from arrays/non-template constructs.
I do not feel the same way about
coutandprintf. Neither is any lower-level than the other, except thatcoutuses operator overloading.This may seem stupid, but I am absolutely fanatic about having people understand the very basic building blocks of everything before moving on to the abstractions. You shouldn't use smart pointers until you're proficient with raw pointers, no vectors before arrays, that sort of thing.
I often say this, but I'll say it again: it's better to teach students long division first and then let them use a calculator than to let them use a calculator then teach them long division afterwards.
As for books to teach beginners, see the master list of good C++ books.