GATE 2016

Question

In 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 uu, and [u][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 the 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?

1. Θ(n2)
2. Θ(n+m)
3. Θ(m2)
4. Θ(n4)             its already discussed but i have some doubts..please help :)

a)The best answer says its by applying BFS

why?

Even if we apply DFS  it will give twin pointer right?

b) what is the significance of this statement

and the memory size is not a constraint

absence of this will make any difference?

c) and why to consider BFS or DFS when u represent a graph as adjacency list itself its O(n+m) and as array is O(n²)  right?

Answer 1

https://gateoverflow.in/39620/gate2016-2-41

First you need to find twins of each node. You can do this using level order traversal (i.e., BFS) once. Time complexity of BFS is Θ(m +n).
And you have to use linked list for representation which is extra space (but memory size is not a constraint here).
Final, time complexity is Θ(m + n)