I’ve tried to implement it in a bit different way than Prateek Bhaiya. Please tell if the code is correct or not.
#include<iostream>
#include<map>
#include<list>
#include<stack>
using namespace std;
template<typename T>
class Graph{
map<T,list<T>> m;
void dfs_helper(T src, map<T,bool> &visited, stack<int> &st){
visited[src] = true;
for(auto nbr:m[src]){
if(!visited[nbr]){
dfs_helper(nbr,visited,st);
st.push(nbr);
}
}
return;
}
public:
void addEdge(T x, T y){
m[x].push_back(y);
}
void dfs(){
map<T,bool> visited;
for(auto p:visited){
visited[p.first] = false;
}
stack<T> st;
for(auto p:m){
if(!visited[p.first]){
dfs_helper(p.first,visited,st);
st.push(p.first);
}
}
while(!st.empty()){
cout<<st.top()<<" ";
st.pop();
}
cout<<endl;
}
};
int main(){
Graph<int> g;
g.addEdge(1,4);
g.addEdge(1,2);
g.addEdge(1,3);
g.addEdge(2,3);
g.addEdge(3,5);
g.addEdge(4,5);
g.addEdge(5,7);
g.addEdge(6,7);
g.addEdge(7,7);
g.dfs();
return 0;
}