pranay_teja
9/15/2018 - 12:39 PM

## Graphs-DFS

``````#include<bits/stdc++.h>
using namespace std;

// #Graphs #BasicProblem
//	https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
// Given graph is a strongly connected directed graph
// (there is atleast 1 path from each vertex to another vertex)

// Testcase
// 1
// 4
// 6
// 0 2
// 0 1
// 1 2
// 2 0
// 2 3
// 3 3
// 2
// Ans: 2 0 1 3

void DFS(vector< vector<int> > AdjL,vector<bool> &visited,int start){
cout<<start<<" ";
visited[start]=true;
// loop through the current vertex's AdjL and recursively DFS if vertex is not visited
}
}
}

int main(){
freopen("ip.txt","r",stdin);
int t;
cin>>t;
while(t--){
int v;
cin>>v;
int e;
cin>>e;
int i=0;
while(i<e){
int a,b;
cin>>a>>b;
i++;
}
vector<bool> visited(v,false);
int start;
// cout<<"Enter starting vertex"<<endl;
cin>>start;
cout<<"DFS: ";
cout<<endl;
//======================(Iterative DFS)==========================
// https://leetcode.com/explore/learn/card/queue-stack/232/practical-application-stack/1385/
for(int i=0;i<v;i++){
visited[i]=false; // reset visited
}
stack<int> st; // contains id's of vertices
st.push(start);
visited[start]=true;
cout<<"Iterative DFS: "<<endl;
while(!st.empty()){
int currTop=st.top(); // store top in temp var
st.pop(); // and pop the current stack
cout<<currTop<<" ";
for(int i=AdjL[currTop].size()-1;i>=0;i--){ //for left to right