Project ForgeIn an adjacency list representation of an undirected simple graph G=(V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E|=m and |V|=n, and memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
- AΘ(n²)
- Θ(n+m)
- CΘ(m²)
- DΘ(n⁴)
Explanation
With enough auxiliary memory (e.g. an n×n array or a hash map keyed by vertex pairs), each of the m edges' two entries can be linked to each other in O(1) time via a single pass building direct-access lookup, giving overall Θ(n+m) — Θ(n) to initialize per-vertex structures plus Θ(m) to process each edge once.
Source: GATE CS 2016 (Session 2 / Set B) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.