Problem

Submissions

Hints & solutions

Discuss

DFS Traversal

Moderate

0/80

Average time to solve is 35m

Contributed by

187 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

2
0 1 2
3 4

Explanation For Sample Input 1:

If we do a DFS traversal from vertex 0 we will get a component with vertices [0, 2, 1]. If we do a DFS traversal from 3 we will get another component with vertices [3, 4]

Hence,  we have two disconnected components so on the first line, print 2. Now, print each component in increasing order. On the first line print 0 1 2 and on the second line, print 3 4.

[0 1 2] comes before [3 4] as the first vertex 0 from the first component is smaller than the first vertex 3 from the second component.

Sample Input 2:

Sample Output 2:

Hint 1

Try to extend the DFS algorithm for this problem. How would you handle the disconnected components? What about performing DFS for each component.

Approaches (1)

Approach 1

DFS For Each Connected Component

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’.

Time Complexity

O(VLogV + E), Where V is the number of vertices and E is the number of edges in the graph.

The time complexity of a DFS is O(V+E) and we are sorting every component which would be VlogV so overall complexity is O(V+E+VlogV) which is O(VlogV+E).

Space Complexity

O(V+E), Where V is the number of vertices and E is the number of edges in the graph.

To store the graph in the adjacency list.

(75% EXP penalty)

(100% EXP penalty)

DFS Traversal

swapnil deshpande

Interview problems

cpp solution using graph

void preparedAdjList(vector<vector<int>> &edges, unordered_map<int, list<int> > &adjList){

for(int i=0;i<edges.size();i++){

int u=edges[i][0];

int v=edges[i][1];

adjList[u].push_back(v);

adjList[v].push_back(u);

}

void dfs(unordered_map<int, list<int>> &adjList, vector<int> &component,unordered_map<int, bool> &visited, int node){

component.push_back(node);

visited[node]=1;

for(auto i:adjList[node]){

if(!visited[i]){

dfs(adjList, component, visited,i);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)

{

// Write your code here

unordered_map<int,list<int>>adjList;

unordered_map<int,bool>visited;

vector<vector<int>>ans;

preparedAdjList(edges,adjList);

for(int i=0;i<V;i++){

if(!visited[i]){

vector<int>component;

dfs(adjList,component,visited,i);

ans.push_back(component);

}

return ans;

}

35 views

0 replies

1 upvote

Manish Raj Pandey

Interview problems

easy cpp

#include<bits/stdc++.h>

using namespace std;

void dfs(vector<int> adj[], vector<int> &visited, vector<int> &ans,int Node) {

visited[Node] = 1;

ans.push_back(Node);

for (auto it : adj[Node]) {

if (!visited[it])

dfs(adj, visited, ans, it);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges) {

vector<int> visited(V, 0);

vector<vector<int>> ans;

vector<int> adj[V];

for(int i=0;i<edges.size();i++){

int u=edges[i][0];

int v=edges[i][1];

adj[u].push_back(v);

adj[v].push_back(u);

}

for (int i = 0; i < V; i++) {

if (!visited[i]) {

vector<int> temp;

dfs(adj, visited, temp, i);

ans.push_back(temp);

}

return ans;

}

138 views

0 replies

0 upvotes

NITISH KUMAR GUPTA

Interview problems

DFS Traversal in cpp

#include <unordered_map>

void dfs(int node, unordered_map<int,bool>&visited, unordered_map<int, list<int>>&adj, vector<int>&component){

component.push_back(node); //store ans

visited[node]=true; //mark visited

//recursive call on connected node

for(auto i:adj[node]){

if(!visited[i]){

dfs(i, visited, adj, component);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)

{

// Write your code here

unordered_map<int,list<int>>adj;

for(int i=0;i<edges.size();i++){

int u = edges[i][0];

int v = edges[i][1];

adj[u].push_back(v);

adj[v].push_back(u);

}

vector<vector<int>>ans;

unordered_map<int,bool>visited;

//for all nodes call DFS, if not visited

for(int i=0;i<V;i++){

if(!visited[i]){

vector<int>component;

dfs(i,visited,adj,component);

ans.push_back(component);

}

return ans;

}

143 views

0 replies

1 upvote

kamlesh gurjar

Interview problems

Rewise it simple but conceptual

#include <list>
#include <unordered_map>


void dfs(unordered_map<int, list<int>> &adj, vector<int> &container,
         vector<bool> &isVisited, int node) {
  container.push_back(node);
  isVisited[node] = true;

  for (auto data : adj[node]) {
    if (!isVisited[data]) {
      dfs(adj, container, isVisited, data);
    }
  }
}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges) {
  unordered_map<int, list<int>> adj;
  vector<bool> isVisited(V, false);
  vector<vector<int>> ans;

  for (int i = 0; i < E; i++) {
    adj[edges[i][0]].push_back(edges[i][1]);
    adj[edges[i][1]].push_back(edges[i][0]);
  }

  for (int i = 0; i < V; i++) {

    if (!isVisited[i]) {
      vector<int> container;
      dfs(adj, container, isVisited, i);
      ans.push_back(container);
    }
  }

  return ans;
}

52 views

0 replies

0 upvotes

Deependra Parmar

Interview problems

Best C++ Solution

void dfs(vector<vector<int>>& adj,unordered_map<int,bool>& visited,vector<int>&ans,int node){
    ans.push_back(node);
    visited[node]=true;
    for(int i=0;i<adj[node].size();i++){
      if(!visited[adj[node][i]]) {
        dfs(adj, visited, ans, adj[node][i]);
      }
    }
}
vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges){
    vector<vector<int>>adj(V);
     for(int i=0;i<edges.size();i++){
        int u=edges[i][0];
        int v=edges[i][1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    vector<vector<int>>ans;
    unordered_map<int,bool>visited;


   for(int i=0;i<V;i++){
       if(!visited[i]){
         vector<int>component;
           dfs(adj,visited,component, i);
           ans.push_back(component);
       }
   }


   return ans;
}

220 views

0 replies

1 upvote

Rachit Joshi

Interview problems

94.69 PERCENT BETTER || C++

void dfs(int node ,unordered_map<int , bool>&visited,unordered_map<int , list<int>>&adj,vector<int>&component ){

component.push_back(node);

visited[node] = true;

for(auto i :adj[node]){

if(!visited[i]){

dfs(i,visited,adj,component);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)

{

// Write your code here

unordered_map<int , list<int>>adj;

for (int i = 0; i < edges.size(); i++) {

int u = edges[i][0];

int v = edges[i][1];

adj[u].push_back(v);

adj[v].push_back(u);

}

vector<vector<int>>ans;

unordered_map<int , bool>visited;

for(int i = 0;i<V;i++){

if(!visited[i]){

vector<int>component;

dfs(i,visited,adj,component);

ans.push_back(component);

}

return ans;

}

104 views

0 replies

0 upvotes

Saumy Singh

Interview problems

C++ Solution for DFS traversal

void dfs(int node,unordered_map<int,bool> &visited,unordered_map<int,list<int>> &adj, vector<int> &component){

//Ans Store

component.push_back(node);

visited[node] = 1;

for(auto i : adj[node]){

if(!visited[i]){

dfs(i,visited,adj,component);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)

{

// Step 1 Prepare Adjacency List

unordered_map<int,list<int>> adj;

// Traverse the Edges

for(int i = 0; i < E; i++){

int u = edges[i][0];

int v = edges[i][1];

//Making Edge

adj[u].push_back(v);

adj[v].push_back(u);

}

vector<vector<int>> ans;

unordered_map<int,bool> visited;

//V is the Number of Vertex Present in the Graph

//For all Nodes call Dfs , if not visited

for(int i = 0; i< V; i++){

if(!visited[i]){

vector<int> component;

dfs(i, visited, adj, component);

ans.push_back(component);

}

return ans;

}

204 views

0 replies

0 upvotes

Abdul Ikram

Interview problems

Easy C++ Solution || All Test Case Passed

#include<bits/stdc++.h>

void dfs(int node, map<int, bool> &visited, unordered_map<int, list<int>> &adj, vector<int> &component){

component.push_back(node);

visited[node] = true;

for(auto i:adj[node]){

if(!visited[i]){

dfs(i, visited, adj, component);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)

{

unordered_map<int, list<int>> adj;

vector<vector<int>> answer;

map<int, bool> visited;

for(int i=0;i<E;i++){

adj[edges[i][0]].push_back(edges[i][1]);

adj[edges[i][1]].push_back(edges[i][0]);

}

for(int i=0;i<V;i++){

if(!visited[i]){

vector<int> component;

dfs(i, visited, adj, component);

answer.push_back(component);

}

return answer;

}

218 views

0 replies

0 upvotes

prakash kundula

Interview problems

step by step cpp soln

void prepareadjlist(int E,unordered_map<int,vector<int>>&adjlist, vector<vector<int>> &edges){

for(int i=0;i<E;i++){

int u = edges[i][0];

int v = edges[i][1];

adjlist[u].push_back(v);

adjlist[v].push_back(u);

}

void dfs(int i,unordered_map<int,bool>&visited,unordered_map<int,vector<int>>&adjlist,vector<int>&component){

component.push_back(i);

visited[i] = 1;

for(auto x: adjlist[i]){

if(!visited[x]){

dfs(x,visited,adjlist,component);

}

vector<vector<int>> depthFirstSearch(int V, int E, vector<vector<int>> &edges)

{

// Write your code here

unordered_map<int,bool>visited;

vector<vector<int>>ans;

unordered_map<int,vector<int>>adjlist;

prepareadjlist(E,adjlist,edges);

for(int i=0;i<V;i++){

vector<int>component;

if(!visited[i]){

dfs(i,visited,adjlist,component);

ans.push_back(component);

}

return ans;

}

131 views

0 replies

0 upvotes

Anirudh Sharma

Interview problems

Java Solution Easy to Understand

import java.util.ArrayList;

public class Solution {
    public static ArrayList<ArrayList<Integer>> depthFirstSearch(int v, int e, ArrayList<ArrayList<Integer>> edges) {
        // Write your code here.

        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer>[] adj = new ArrayList[v];
        for(int i = 0; i<v; i++){
            adj[i] = new ArrayList<>();
        }

        for(ArrayList<Integer> it : edges){
            int u = it.get(0);
            int V = it.get(1);

            adj[u].add(V);
            adj[V].add(u);
        }

        boolean[] visited = new boolean[v];

        for(int i = 0; i<v; i++){
            if(!visited[i]){
                ArrayList<Integer> temp = new ArrayList<>();
                dfs(i,visited,adj,temp);
                ans.add(temp);
            }
        }

        return ans;
    }

    private static void dfs(int node ,boolean[] visited,ArrayList<Integer>[] adj,ArrayList<Integer> temp){
        temp.add(node);
        visited[node] = true;
        for(Integer nbr : adj[node]){
            if(!visited[nbr]){
                dfs(nbr, visited, adj, temp);
            }
        }
    }
}

195 views

0 replies

1 upvote

Console