GATE 2025 DA – Question 65
Consider a directed graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, 100\}$ and $E = \{(i, j) : 0 < j - i \le 2, \text{ for all } i, j \in V\}$. Suppose the adjacency list of each vertex is in decreasing order of vertex number, and depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after vertex 50 is ______ (*Answer in integer*)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 75
Explanation
Each vertex $i$ has edges to $i + 1$ and $i + 2$, listed with the larger one first. From 0 the DFS takes the larger neighbour every time, so it discovers 0, 2, 4, ..., 100. At 100 there are no edges, so it backtracks. At 98, the neighbour 100 is already visited and 99 is new, so 99 is discovered. Going back through 96, 94, ..., 0, each even vertex $i$ then finds its neighbour $i + 1$ unvisited and discovers it, so 97, 95, ..., 1 follow. Vertex 50 is discovered while going down the even vertices, so what comes after it are the even vertices 52 to 100 (25 of them) and all 50 odd vertices 1 to 99, which is 75 vertices.