Question 51

In an undirected graph $G = (V, E)$, every undirected edge $\{u, v\}$ is stored as two directed adjacency list nodes: $[v]$ in the list for vertex $u$, and $[u]$ in the list for vertex $v$. Since $|E| = m$, there are exactly $2m$ such nodes in total across all $|V| = n$ lists.

Each list node can be viewed as an edge tuple $(u, v, \text{node\_ptr})$, where $u$ is the list owner, $v$ is the neighbor, and $\text{node\_ptr}$ points to the entry in $u$'s list. Traversing all adjacency lists to collect all $2m$ tuples takes $\Theta(n + m)$ time.

To pair each directed entry $(u, v)$ with its twin $(v, u)$, normalize the endpoints so the pair is keyed by $(\min(u, v), \max(u, v))$. Because vertex indices are integers from $1$ to $n$, we can sort the $2m$ tuples using two passes of Counting Sort (Radix Sort with base $n$).

Sorting $2m$ tuples with integer keys in the range $[1, n]$ takes $\Theta(n + m)$ time and $\Theta(n + m)$ auxiliary memory. After sorting, twin entries appear consecutively in pairs. A single pass over the sorted array takes $\Theta(m)$ time to set the twin pointer in each node to point to the other node.

Therefore, the total time complexity of the most efficient algorithm is $\Theta(n + m)$.