[Jach]

Neat structure! I consulted my copy of Skiena's Algorithm Design Manual. He says: "Union-find is a fast, simple data structure that every programmer should know about." Well... Now I do. :) It is simple, a 'backwards' tree with pointers from a node to its parent, which lets you union two separate trees together by just taking the shorter one's root and pointing it at the taller one's (or vice versa, but this way preserves log behavior). The path compression optimization seems to just be an extra pass in find(), after you have the result, to re-parent each item along the path to the found root parent so that any future finds() of any of those items will only have one lookup to reach the component root.

For the jump game problem, I'd expect DFS would still win almost all the time even when there are many branches because it doesn't have to explore every element of the input array except in the worst case (and you can greedily explore a neighbor without having to discover your other neighbors first), whereas to build a complete union-find structure would. Still, the fastest solution in general is probably just the single pass: if you have the insight that you can keep track of a 'max reachable index' and update it at each step to max(current-max, i + A[i]), bailing with failure if you hit an index > the current max and having no more jumps, or bailing with success if your max becomes >= the final index. (I never had this insight myself.) It could be slower of course, e.g. if the array was something like [bigNum/2, lots of 0s, bigNum/2 again in the middle, lots of 0s, end at index bigNum].