# Special arcs - graph traversal

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)?

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)$$.
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|)$$.