The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is _________

Answer: 60Concept -- DFS Forest and Connected Components (from Cormen et al., Introduction to Algorithms):When DFS is performed on an undirected graph G with n vertices and the resulting DFS forest (spanning forest) has e edges, each tree in the DFS forest corresponds to exactly one connected component of G.A spanning tree of a connected component with k vertices has exactly k-1 edges. If there are c connected components with sizes k_1, k_2, ..., k_c, then:Total edges in DFS forest = sum(k_i - 1) = sum(k_i) - c = n - c.Given: n = 100, edges in DFS forest = 40.40 = 100 - c. c = 100 - 40 = 60.

GATE-CS is a competitive examination conducted in India. This question is from the 2024 GATE-CS Algorithm paper.

How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2024 question covers Graph Traversals (BFS and DFS) topic.

What is the difficulty level of this question?

This GATE-CS 2024 Algorithm question has a easy difficulty level and is marked as an important question.

Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

GATE-CS Algorithm 2024 - The number of edges present in...

An undirected simple graph G(V,E) is 2-colorable if there exists c: V --> {0,1} such that for every …

MEDIUM2026GATE-CSAlgorithm

The given DFS algorithm computes d[v] (discovery time) and f[v] (finishing time) for each vertex. Th…

HARD2026GATE-CSAlgorithm

Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of …

HARD2025GATE-CSAlgorithm

Which of the following statements regarding BFS and DFS on an undirected simple graph G is/are TRUE?

MEDIUM2025GATE-CSAlgorithm

someAlgo(G): (1) BFS from any v, find farthest vertex u. (2) BFS from u, find farthest vertex z. (3)…

MEDIUM2025GATE-CSAlgorithm

Let G be a directed graph and T a DFS spanning tree in G rooted at vertex v. Suppose T is also a BFS…

HARD2024GATE-CSAlgorithm

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is _________

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions

The number of edges present in the forest generated by the DFS traversal of an undirected graph G with 100 vertices is 40. The number of connected components in G is _________

Master GATE-CS with Our Test Series

More Questions from Graph Traversals (BFS and DFS)

Frequently Asked Questions