Some helpful ADT's for working with directed graphs

bag.hpp

#ifndef bag_hpp
#define bag_hpp

template <class T>
class BagIter {
    private:
        T* curr;
    public:
        BagIter(T* pos) {
            curr = pos;
        }
        T& operator*() {
            return *curr;
        }
        BagIter operator++() {
            ++curr;
            return *this;
        }
        BagIter operator++(int) {
            curr++;
            return *this;
        }
        bool operator==(const BagIter& it) const {
            return curr == it.curr;
        }
        bool operator!=(const BagIter& it) const {
            return !(*this == it);
        }
};

template <class T>
class Bag {
    private:
        using iterator = BagIter<T>;
        T* data;
        int n;
        int maxn;
        void grow() {
            cout<<" (grow)"<<endl;
            T* tmp = new T[2*maxn];
            for (int i = 0; i < n; i++)
                tmp[i] = data[i];
            delete [] data;
            data = tmp;
            maxn *= 2;
        }
    public:
        Bag() {
            n = 0;
            maxn = 2;
            data = new T[maxn];
        }
        Bag(const Bag& b) {
            n = b.n;
            maxn = b.maxn;
            data = new T[maxn];
            for (int i = 0; i < b.n; i++)
                data[i] = b.data[i];
        }
        ~Bag() {
            delete [] data;
        }
        int size() {
            return n;
        }
        bool empty() {
            return size() == 0;
        }
        void add(T item) {
            if (n+1 == maxn)
                grow();
            data[n++] = item;
        }
        void clear() {
            n = 0;
        }
        iterator begin() {
            return BagIter<T>(data);
        }
        iterator end() {
            return BagIter<T>(data+n);
        }
        Bag& operator=(const Bag& b) {
            n = b.n;
            maxn = b.maxn;
            data = new T[maxn];
            for (int i = 0; i < b.n; i++)
                data[i] = b.data[i];
            return *this;
        }
};

#endif

dfs.hpp

#ifndef dfs_hpp
#define dfs_hpp
#include "stack.hpp"
#include "digraph.hpp"

class DFS {
    private:
        bool *seen;
        void init(int numv) {
            seen = new bool[numv];
            for (int i = 0; i < numv; i++)
                seen[i] = false;
        }
        void dfs(Digraph& g, int vertex) {
            seen[vertex] = true;
            for (Edge next : g.adj(vertex))
                if (!seen[next.to])
                    dfs(g, next.to);
        }
    public:
        DFS(Digraph& g, int src) {
            init(g.V());
            dfs(g, src);
        }
        DFS(Digraph& g, Bag<int>& src) {
            init(g.V());
            for (int v : src)
                if (!seen[v])
                    dfs(g, v); 
        }
        bool marked(int vertex) {
            return seen[vertex];
        }
};

#endif

digraph.hpp

#ifndef digraph_hpp
#define digraph_hpp
#include "bag.hpp"

struct Edge {
    int from;
    int to;
    Edge(int f, int t) : from(f), to(t) { }
};

class Digraph {
    private:
        Bag<Edge>* adjlist;
        int nume;
        int numv;
    public:
        Digraph(int nv) {
            numv = nv;
            nume = 0;
            adjlist = new Bag<Edge>[nv];
        }
        Digraph(const Digraph& dg) {
            numv = dg.numv;
            nume = 0;
            adjlist = new Bag<Edge>[numv];
            for (int i = 0; i < dg.numv; i++) {
                for (Edge e : dg.adjlist[i]) {
                    addEdge(e.from, e.to);
                }
            }
        }
        ~Digraph() {
            delete [] adjlist;
        }
        void addEdge(int from, int to) {
            if (!hasEdge(from, to)) {
                adjlist[from].add(Edge(from,to));
                nume++;
            }
        }
        Bag<Edge>& adj(int v) {
            return adjlist[v];
        }
        bool hasEdge(int v, int u) {
            for (Edge e : adjlist[v])
                if (e.to == u)
                   return true;
            return false;
        }
        int V() {
            return numv;
        }
        int E() {
            return nume;
        }
        Digraph& operator=(const Digraph& dg) {
            numv = dg.numv;
            nume = 0;
            adjlist = new Bag<Edge>[numv];
            for (int i = 0; i < dg.numv; i++) {
                for (Edge e : dg.adjlist[i]) {
                    addEdge(e.from, e.to);
                }
            }
            return *this;
        }
};

#endif

stack.hpp

#ifndef stack_hpp
#define stack_hpp

template <class T>
class Stack {
    private:
        T* data;
        int n;
        int maxn;
        void grow() {
            T* tmp = new T[2*maxn];
            for (int i = 0; i < n; i++)
                tmp[i] = data[i];
            delete [] data;
            data = tmp;
            maxn *= 2;
        }
    public:
        Stack() {
            n = 0;
            maxn = 2;
            data = new T[maxn];
        }
        Stack(const Stack& b) {
            n = b.n;
            maxn = b.maxn;
            data = new T[maxn];
            for (int i = 0; i < b.n; i++)
                data[i] = b.data[i];
        }
        ~Stack() {
            delete [] data;
        }
        int size() {
            return n;
        }
        bool empty() {
            return size() == 0;
        }
        void push(T item) {
            if (n+1 == maxn)
                grow();
            data[n++] = item;
        }
        T& top() {
            return data[n-1];
        }
        T pop() {
            return data[--n];
        }
        void clear() {
            n = 0;
        }
        Stack& operator=(const Stack& b) {
            n = b.n;
            maxn = b.maxn;
            data = new T[maxn];
            for (int i = 0; i < b.n; i++)
                data[i] = b.data[i];
            return *this;
        }
};

#endif