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