22.1-4 solution has no proof of algorithm complexity

[faucct]

if the neighbor is not already present in the new adjacency list of u

Traversing through adjacency list could take N operations if the adjacency list is full. It should be explicitly stated that there is no need to. There are two cases depending on if we have already traversed the neighbour adjacency list in initial multigraph. If we did then we have already added u there during that traverse. If no then you should only check if u is a first element of neighbour adjacency list as we could not add anything else after it during current traverse. This solution only works if initial multigraph is undirected. Am I understanding right if this is the case?

[walkccc]

Hey, try this: https://walkccc.github.io/CLRS/Chap22/22.1/#221-4

[faucct]

It made me think for a while, but it is a nice one! Maybe it could have more proof in it to ease understanding.

[walkccc]

I've rewritten the answer and tried to make it more readable!

[faucct]

Now it is the same as one I have created this issue about and is wrong because of the same reason. :( When you check if v belongs to new adjacency list of u it can take N operations and the algorithm complexity will be O(V + E * V).

[walkccc]

I know what you were talking about! I've corrected the solution with a matrix M of size |V|^2. Please check it!

[faucct]

It is simple and correct now. Thanks. This repo should use it too.

[walkccc]

Thanks, too. You can try to search solutions in my website if any further help is needed: http://walkccc.github.io/CLRS