Register

GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 38

• retagged by
431 views
1 1 vote

Suppose the input directed graph $G(V,E)$ is a DAG. For an edge $(u,v)\in E$, which of the following will NEVER be correct in DFS discovery/finish times?

  1. $d[u] < d[v] < f[v] < f[u]$
     
  2. $d[v] < d[u] < f[u] < f[v]$
     
  3. $d[u] < f[u] < d[v] < f[v]$
     
  4. $d[v] < f[v] < d[u] < f[u]$

1 Answer

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2026 | Set ...Next → · GO Classes | IIITH P...
← Previous in category · GATE CSE 2026 | Set ...Next in category → · Memory Based 2026 as...
Position:
Show:

Related questions

2 2 votes
1 1 answer
610
610 views
GO Classes asked Feb 12
610 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 36
If there is no path from $\delta$ to a of length at most k , then $d_k(u)=\infty$Statement 1: For every $u \geq 0$ and $u \in V, d_{k+1}(u) \leq d_k(u)$.Statement 2: For ...
0 0 votes
1 1 answer
444
444 views
GO Classes asked Feb 12
444 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 33
Let $\mathrm{G}(\mathrm{V}, \mathrm{E})$ be a simple, undirected, edge-weighted graph with unique edge weights.Which of the following statements about MST (minimum spanni...
4 4 votes
2 2 answers
518
518 views
GO Classes asked Feb 12
518 views
GATE CSE 2026 | Set 1 | Algorithms | Memory Based | Question 34
Consider the following:For all $n>1$$$\begin{aligned}& T_1(n)=4 T_1(n / 2)+T_2(n) \\\\& T_2(n)=5 T_2(n / 4)+\theta\left(\log _2 n\right)\end{aligned}$$Assume that for all...
1 1 vote
1 1 answer
955
955 views
GO Classes asked Feb 4, 2024
955 views
Memory Based GATE DA 2024 | Question: 27
Consider performing Depth-First Search (DFS) on an undirected and unweighted graph $\bar{G}$ starting at vertex $S$. For any vertex $u$ in $G$, where $d[u]$ is the length...