GATE CSE 2024 Session 1 Q60: Connected components from the size of a DFS forest
- Algorithms
- 2 marks
- NAT
- No negative marking
Question
The number of edges present in the forest generated by the DFS traversal of an undirected graph with 100 vertices is 40. The number of connected components in is _________
Try it: numerical answer: type the value
Numerical answer. No negative marking.
Show answer and explanation
Answer: 60 (official GATE 2024 final answer key)
Concept used: A spanning forest with trees on vertices has edges.
First step: Solve .
Full step-by-step solution
Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.
Share this question
Source: official GATE 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key
More Algorithms PYQs
- 2026 Session 1 · Q17Solve nested recurrences T1 = 4T1(n/2) + T2, T2 = 5T2(n/4) + log n
- 2026 Session 1 · Q41Shortest paths with at most k edges: two statements
- 2026 Session 1 · Q47Condition forcing a vertex into every minimum vertex cover
- 2026 Session 1 · Q49Cycle and cut properties of MSTs with distinct weights
- 2026 Session 1 · Q50Impossible DFS discovery/finish orderings for a DAG edge
- 2026 Session 1 · Q55Properties of 2-colorable (bipartite) graphs