#include <iostream>
//#include "Stack.cpp"
//#include "Queue.cpp"

#ifndef NULL_VALUE
#define NULL_VALUE -999999
#endif

#ifndef INFINITY
#define INFINITY 999999
#endif

template <class T>
class Stack
{
public:
  Stack (int);   // create a stack with given capacity
  ~Stack();
  void push(T);  // push at the end
  void pop();    // pop from the end
  T peek();      // return the last item
  int size() { return top+1; }

private:
  T * arr;
  int capacity;
  int top;
};

template <class T>
Stack<T>::Stack(int capacity) {
  this->capacity = capacity;
  top = -1;
  arr = new T[capacity];
}

template <class T>
Stack<T>::~Stack() {
  if (arr) delete[] arr;
  arr = NULL;
}

template <class T>
void Stack<T>::push(T value) {
  if (size() >= capacity) {
    std::cout << "Stack is full." << std::endl;
    return ;
  }

  top++;
  arr[top] = value;
}

template <class T>
void Stack<T>::pop() {
  if (size() <= 0) {
    std::cout << "Stack is empty." << std::endl;
    return ;
  }
  top--;
}

template <class T>
T Stack<T>::peek() {
  if (size() <= 0)
    return NULL_VALUE;
  return arr[top];
}


template <class T>
class Queue
{
public:
  Queue (int);      // create queue with given capacity
  ~Queue();
  void enqueue(T);  // push item at the last
  void dequeue();  // pop item from the beginning
  T first();        // return item at the beginning
  T last();         // return item at the end
  int size();       // return the size

private:
  T * arr;
  int capacity;
  int head;
  int tail;
  int length;
};

template <class T>
Queue<T>::Queue(int capacity) {
  this->capacity = capacity;
  head = 0;
  tail = -1;
  length = 0;
  arr = new T[capacity];
}

template <class T>
Queue<T>::~Queue() {
  if (arr) delete[] arr;
  arr = NULL;
}

template <class T>
void Queue<T>::enqueue(T value) {
  if (size() >= capacity) {
    std::cout << "Queue is full." << std::endl;
    return ;
  }

  tail = ( tail + 1 ) % capacity;
  arr[tail] = value;
  length++;
}

template <class T>
void Queue<T>::dequeue() {
  if (size() <= 0) {
    std::cout << "Queue is empty." << std::endl;
    return ;
  }

  head = ( head + 1 ) % capacity;
  length--;
}

template <class T>
T Queue<T>::first() {
  if (size() <= 0) return NULL_VALUE;
  return arr[head];
}

template <class T>
T Queue<T>::last() {
  if (size() <= 0) return NULL_VALUE;
  return arr[tail];
}

template <class T>
int Queue<T>::size() {
  return length;
}


class Graph {
public:
  Graph(bool, int, int);
  ~Graph();
  bool isEdge(int, int);
  void addEdge(int u, int v);
  void removeEdge(int u, int v);
  int getDegree(int u);
  void dfs(int);
  void bfs(int);
  void topSort(int);
private:
  bool isDirected;
  int ** adjMat;
  int noOfVertices;
  int noOfEdges;
  Stack<int> * tmpStack;
};

Graph::Graph(bool isDirected, int noOfVertices, int noOfEdges) {
  this->isDirected = isDirected;
  this->noOfVertices = noOfVertices;
  this->noOfEdges = noOfEdges;
  adjMat = new int * [noOfVertices];
  for (int i=0; i<noOfVertices; i++) {
    adjMat[i] = new int[noOfVertices];
    for (int j=0; j<noOfVertices; ++j)
      adjMat[i][j] = 0;
  }

  tmpStack = new Stack<int>(noOfVertices);
}

Graph::~Graph() {
  for (int i=0; i<noOfVertices; ++i)
    if (adjMat[i])
      delete[] adjMat[i];
  if (adjMat) delete[] adjMat;
  adjMat = NULL;
}

bool Graph::isEdge(int u, int v) {
  return adjMat[u][v];
}

void Graph::addEdge(int u, int v)
{
  if(u<0 || u>=noOfVertices || v<0 || v>=noOfVertices) return;
  adjMat[u][v] = 1;
  if(!isDirected) adjMat[v][u] = 1;
}

void Graph::removeEdge(int u, int v)
{
  if (u<0 || u>=noOfVertices || v<0 || v>=noOfVertices) return;
  adjMat[u][v] = 0;
  if (!isDirected) adjMat[v][u] = 0;
}

void Graph::dfs(int source) {
  if (source <0 || source >= noOfVertices) return;

  bool * visited = new bool[noOfVertices];
  bool * adjVertex = new bool[noOfVertices];
  for (int i=0; i<noOfVertices; ++i)
    visited[i] = false;

  Stack<int> st(noOfVertices);
  st.push(source);

  while (st.size() > 0) {
    source = st.peek();
    st.pop();
    visited[source] = true;
    tmpStack->push(source);
    std::cout << source << " " ;

    int noOfAdjVertices = 0;
    for (int i=0; i<noOfVertices; ++i) {
      if (isEdge(source, i)) {
        noOfAdjVertices++;
        adjVertex[i] = true;
      } else
        adjVertex[i] = false;
    }

    for (int i=0; i<noOfVertices; ++i) {
      if (!adjVertex[i]) continue;
      else if (!visited[i]) {
        st.push(i);
      }
    }
  }
  std::cout << std::endl;
}

void Graph::bfs(int source) {
  if (source <0 || source >= noOfVertices) return;

  bool * adjVertex = new bool[noOfVertices];
  bool * visited = new bool[noOfVertices];
  for (int i=0; i<noOfVertices; ++i) {
    visited[i] = false;
  }

  Queue<int> q(noOfVertices);
  q.enqueue(source);
  visited[source] = true;
  std::cout << source << " ";

  while (q.size() > 0) {
    source = q.first();
    q.dequeue();

    int noOfAdjVertices = 0;
    for (int i=0; i<noOfVertices; ++i) {
      if (isEdge(source, i)) {
        noOfAdjVertices++;
        adjVertex[i] = true;
      } else
        adjVertex[i] = false;
    }
    for (int i=0; i<noOfVertices; ++i) {
      if (!adjVertex[i]) continue;
      else if (!visited[i]) {
        q.enqueue(i);
        visited[i] = true;
        std::cout << i << " ";
      }
    }
  }
  std::cout << std::endl;
}

void Graph::topSort(int source) {
  dfs(source);
  while(tmpStack->size() > 0) {
    std::cout << tmpStack->peek() ;
    tmpStack->pop();
  }
}

int main() {
  Graph g(true, 5, 6);
  g.addEdge(0,1);
  g.addEdge(0,3);
  g.addEdge(1,2);
  g.addEdge(1,3);
  g.addEdge(2,4);
  g.addEdge(3,2);
  g.topSort(0);

  return 0;
}