Question:
Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and
\[ E = \{(i,j) : 0 < j - i \leq 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:
Consider a directed graph \( G = (V,E) \), where \( V = \{0,1,2,\dots,100\} \) and
\[ E = \{(i,j) : 0 < j - i \leq 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:
Show Hint
When DFS is performed with an adjacency list sorted in decreasing order, higher-numbered vertices are visited first, affecting the traversal order significantly.
Updated On: Feb 3, 2026
Show Solution
Verified By Collegedunia
Solution and Explanation
Step 1: Understanding the graph structure.
Each vertex \( i \) has directed edges to \( i+1 \) and \( i+2 \), if they exist.
The adjacency list is sorted in decreasing order, meaning DFS explores the highest-numbered neighbor first.
Step 2: DFS traversal starting from vertex 0.
DFS starts at 0 and always visits the highest-numbered connected vertex first.
This results in the traversal order: 0, 2, 4, ..., reaching 100 first.
After backtracking, vertices in the range \( 1, 3, 5, \dots \) get visited.
Step 3: Counting vertices discovered after vertex 50.
Since DFS reaches 100 before backtracking, all vertices from 51 to 100 are discovered after 50.
The number of such vertices is \( 100 - 25 = 75 \).
Thus, the number of vertices discovered after vertex 50 is: \[ 75. \]
Each vertex \( i \) has directed edges to \( i+1 \) and \( i+2 \), if they exist.
The adjacency list is sorted in decreasing order, meaning DFS explores the highest-numbered neighbor first.
Step 2: DFS traversal starting from vertex 0.
DFS starts at 0 and always visits the highest-numbered connected vertex first.
This results in the traversal order: 0, 2, 4, ..., reaching 100 first.
After backtracking, vertices in the range \( 1, 3, 5, \dots \) get visited.
Step 3: Counting vertices discovered after vertex 50.
Since DFS reaches 100 before backtracking, all vertices from 51 to 100 are discovered after 50.
The number of such vertices is \( 100 - 25 = 75 \).
Thus, the number of vertices discovered after vertex 50 is: \[ 75. \]
Was this answer helpful?
0
0
Top GATE DA Computer Science Questions
- def outer():
x = []
def inner(val):
x.append(val)
return x
return inner
f1 = outer()
f2 = outer()
print(f1(10)) \# line P
print(f1(20)) \# line Q
print(f2(30)) \# line R
print(f1(40)) \# line S
Which of the following is/are correct? A recursive function is given:
def mystery(n):
if n $<=$ 0:
return 1
else:
return mystery(n-1) + mystery(n-2)
Find the value of mystery(4).- Assume a typical runtime stack is used for the recursive function mystery(n) as defined earlier. How many total function calls (stack activations), including the initial call, are made to compute mystery(4)?
def fun(L, i=0):
if i $>=$ len(L) - 1:
return 0
if L[i]> L[i+1]:
L[i+1], L[i] = L[i], L[i+1]
return 1 + fun(L, i+1)
else:
return fun(L, i+1)
data = [5, 3, 4, 1, 2]
count = 0
for _ in range(len(data)):
count += fun(data)
print(count)
- def append_to_lst(val, lst=[]):
lst.append(val)
return lst
print(append_to_lst(1))
print(append_to_lst(2))
print(append_to_lst(3, []))
Top GATE DA Questions
- Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during the above DFS, then (u, v) becomes a _____ edge.
- Three fair coins are tossed independently. T is the event that two or more tosses result in heads. S is the event that two or more tosses result in tails. What is the probability of the event T ∩ S?
- Consider the matrix \(M=\begin{bmatrix} 2 & -1 \\ 3 & 1 \end{bmatrix}\).
Which ONE of the following statements is TRUE ? - For any twice differentiable function ƒ: R → R, if at some x* ∈ R, f'(x*) = 0 and f'(x*) > 0, then the function f necessarily has a ______ at x = x*.
Note : R denotes the set of real numbers. - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables
View More Questions