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)
Answer
75
Explanation
Each vertex \(i\) has edges only to \(i + 2\) and \(i + 1\), listed in that order. So DFS from 0 always follows the \(+2\) edge first: 0, 2, 4, …, 100. Vertex 100 has no outgoing edges, so DFS backtracks to 98, whose second neighbour 99 is new; back at 96 it finds 97, and so on down to 1.
The discovery order is 0, 2, 4, …, 100, then 99, 97, …, 1. Vertex 50 is the 26th vertex discovered, so the other \(101 - 26 = 75\) vertices come after it: the 25 even vertices 52 to 100 and all 50 odd vertices.
Answer: 75