Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 25 Jul, 2020

DFS Traversal

Moderate
Asked in companies
SamsungIntuitGoldman Sachs

Problem statement

Given an undirected and disconnected graph G(V, E), containing 'V' vertices and 'E' edges, the information about edges is given using 'GRAPH' matrix, where i-th edge is between GRAPH[i][0] and GRAPH[i][1]. print its DFS traversal.

V is the number of vertices present in graph G and vertices are numbered from 0 to V-1. 

E is the number of edges present in graph G.
Note :
The Graph may not be connected i.e there may exist multiple components in a graph.
Input Format :
The first line of input will contain two Integers V and E, separated by a single space.

From the second line onwards, the next 'E' lines will denote the undirected edge of the graphs. 

Every edge is defined by two single space-separated integers 'a' and 'b', which signifies an edge between the vertices 'a' and 'b'.
Output Format :
The first line of output will contain the size of the connected components.

For every connected component in the graph, print the vertices of the component in the sorted order of the vertex values separated with a single space.

Print each component in on a different line by making sure that the first vertex of each component is also sorted on the vertex values. 

A component having a smaller first vertex in sorted order will come first.
Constraints :
2 <= V <= 10^3
1 <= E <= (5 * (10^3))

Time Limit: 1sec

Approaches

01 Approach

  • Run a loop from 0 to V-1 and if this vertex is not visited do a DFS from this vertex and add all the reachable vertex to a vector/list ‘singleComponent’.
  • Sort the singleComponent vector/list in increasing order and add it to the answer vector/list which is called ‘components’.
  • Print the size of the vector/list ‘components’ on the first line.
  • On each line after the first, print one single component from the vector/list ‘components’.