Special arcs - graph traversal

Question

question is: given an unwighted nondirected graph G=(V,E) portrayed as an adjacency list, a special arc is defined as an arc (u,v) where both u and v has the same distance from source vertex s.

i need to give an algorithm to find all of the special arcs for a given s node.

the teacher's solution is: run BFS from s and save distances from s in every node. then, go over all of the nodes and for every node, check if 1 of the neighbors has same distance.

they claim its complexity is O(|V|+|E|) .. i think it is not.. if all nodes are connected to all nodes then for every node we check we go through all of the nodes so isn't it O(|V|^2)?

Answer 1

Run BFS from source vertex $s$ to find length of shortest path from $s$ to all other vertices in $O(V+E)$.

After than, traverse all edges $(u,v)$, let $d[u]$ be shortest distance of vertex $u$ from $s$, if $d[u]=d[v]$ then report that edge as a special arc. We traverse each edge one time and checking whether end points of edge $(u,v)$ have the same distance from source or not, it's obvious that can be done in $O(1)$.

So the total running time will be $O(V+E)$.

Answer 2

If you have a clique then the complexity is $O(|V|^2)$ as you claim, but $|E| \in \Theta(|V|^2)$ so $O(|V|^2) = O(|E|)$.