#include<iostream>
#include<vector>
using namespace std;


class Graph{
private:
    int n; //number of vertex in the graph
    vector<int>* matrix;
    void DFSUtil(int u, bool visited[]);
public:
    Graph(int n=10){
        this->n = n;
        matrix = new vector<int>[n];
        for(int i=0; i<n; i++){
            matrix[i]= vector<int>();
        }
    }
    void addEdge(int u, int v); // function to add an edge to graph
    void displayMatrix();
    void DFS(int v);
};


void Graph::DFSUtil(int u, bool visited[]){
    visited[u] = true;
    cout << u << " ";
    for(int i=0; i<n; i++){
        if(!visited[i] && matrix[u][i]!=0)
            DFSUtil(i, visited);
    }


}
void Graph::DFS(int v){
    bool *visited = new bool[n];
    for (int i = 0; i < n; i++)
        visited[i] = false;
    DFSUtil(v, visited);
}


void Graph::addEdge(int u, int v) {
    matrix[u].push_back(v);
}

void Graph::displayMatrix() {
    if(n==0) return;
    cout<<"  ";
    for(int i = 0; i < n; i++) cout<<i<<" ";
    cout<<endl;
    for(int i = 0; i < n; i++) cout<<"---";
    cout<<endl;
    for(int i = 0; i < n; i++) {
      cout<<i<< "|";
      for(int j = 0; j < n; j++) {
         cout << matrix[i][j] << " ";
      }
      cout << endl;
    }
}

int main() {
    int n = 4;    //there are 6 vertices in the graph
    Graph g(n);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 1);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(2, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
 //   g.displayMatrix();
    g.DFS(2);

    return 0;
}