As pointed out to me after class, initializing the arrays in DepthFirstPaths.java probably needs time proportional to V (unless we know that their memory is zeroed out already, which we probably don't). So, I should not have said that DepthFirstPaths requires O(E) time. It is also O(V+E) time, just like CC. In ../book/CC.java (from http://algs4.cs.princeton.edu/code/algs4.jar) we found a bug. Where it says this: size[v]++; it should say this: size[count]++; But this bug is fixed in their other online versions of CC.java: http://algs4.cs.princeton.edu/41undirected/CC.java.html http://algs4.cs.princeton.edu/41undirected/CC.java And the textbook completely omits the size method and its array.