DFS Traversal Problem Statement

Given an undirected and disconnected graph G(V, E), where V is the number of vertices and E is the number of edges, the connections between vertices are provided in the 'GRAPH' matrix. Each element of the matrix denotes an edge between two vertices.

Input:

The first line of input contains two integers, V and E, separated by a space.
Following this line are E lines, each containing two space-separated integers a and b, indicating an undirected edge between vertices a and b.

Output:

The first line should print the number of connected components in the graph.
For each connected component, list its vertices in ascending order, separated by spaces.
Each connected component should be printed on a new line, starting with the component that has the smallest vertex number.

Example:

Input:
5 3
0 1
1 2
3 4
Output:
2
0 1 2
3 4
Explanation:

The graph has 5 vertices and 3 edges, forming two connected components: one with vertices 0, 1, and 2; and another with vertices 3 and 4.

Constraints:

  • 2 <= V <= 10^3
  • 1 <= E <= 5 * 10^3
  • Time Limit: 1 sec
Note
The graph might not be connected, which means there may be multiple components.
Be the first one to answer
Add answer anonymously...
Goldman Sachs Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
Awards 2025
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits
Stay ahead in your career with AmbitionBox app