GATE 2016 CS (CS2) – Question 51

Programming and Data Structures · Graphs · 2 marks · Multiple choice

Each edge of a simple undirected graph has two adjacency-list entries, one at each endpoint. A twin pointer connects these entries. With n vertices, m edges and unrestricted memory, what is the most efficient time to set all twin pointers?

$\Theta(n^2)$
$\Theta(n+m)$
$\Theta(m^2)$
$\Theta(n^4)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\Theta(n+m)$

Explanation

Group entries by unordered endpoint pairs using radix/counting sorting of integer vertex IDs. This costs Θ(n+m); a scan pairs the two entries for every edge and sets both pointers. Reading all vertices and adjacency entries already costs Ω(n+m), so Θ(n+m), B, is optimal.