Graph

#include <vector>
#include <unordered_set>
#include <iostream>

class IGraph
{
public:
    typedef std::vector<int> TVertexCollection;
    virtual void AddEdge(int from, int to) = 0;

    virtual size_t VertexCount() const = 0;

    virtual TVertexCollection GetNextVertices(int vertex) const = 0;
    virtual TVertexCollection GetPreviousVertices(int vertex) const = 0;
    virtual ~IGraph() {}
};

class CListGraph;
class CArcGraph;
class CListGraph;
class CMatrixGraph;
class CSetGraph;

class CListGraph : public IGraph
{
public:
    CListGraph(size_t n)
    {
        list.resize(n);
    }

    CListGraph(const CArcGraph& g);
    CListGraph(const CMatrixGraph& g);
    CListGraph(const CSetGraph& g);

    void AddEdge(int from, int to) override
    {
        list[from].push_back(to);
    }

    size_t VertexCount() const override
    {
        return list.size();
    }

    TVertexCollection GetNextVertices(int vertex) const override
    {
        return list[vertex];
    }

    TVertexCollection GetPreviousVertices(int vertex) const override
    {
        std::vector<int> ans;
        for (int i = 0; i < list.size(); i++)
        {
            for (int j = 0; j < list[i].size(); j++)
            {
                if (list[i][j] == vertex)
                {
                    ans.push_back(i);
                    break;
                }
            }
        }
        return ans;
    }
private:
    std::vector<std::vector<int>> list;
};

class CMatrixGraph : public IGraph
{
public:
    CMatrixGraph(size_t n)
    {
        matrix.resize(n, std::vector<int>(n));
    }

    CMatrixGraph(const CArcGraph& g);
    CMatrixGraph(const CListGraph& g);

    CMatrixGraph(const CSetGraph& g);
    void AddEdge(int from, int to) override
    {
        matrix[from][to] = 1;
    }

    size_t VertexCount() const override
    {
        return matrix.size();
    }

    TVertexCollection GetNextVertices(int vertex) const override
    {
        std::vector<int> ans;
        for (int i = 0; i < matrix.size(); i++)
        {
            if (matrix[vertex][i] == 1)
                ans.push_back(i);
        }
        return ans;
    }
    TVertexCollection GetPreviousVertices(int vertex) const override
    {
        std::vector<int> ans;
        for (int i = 0; i < matrix.size(); i++)
        {
            if (matrix[i][vertex] == 1)
                ans.push_back(i);
        }
        return ans;
    }
private:
    std::vector<std::vector<int> > matrix;
};

class CSetGraph : public IGraph
{
public:
    CSetGraph(int n)
    {
        list.resize(n);
    }
    CSetGraph(const CArcGraph& g);
    CSetGraph(const CListGraph& g);
    CSetGraph(CMatrixGraph g)
    {
        int a = g.VertexCount();
        list.resize(a);
        TVertexCollection next;
        for (int i = 0; i < a; i++)
        {
            next = g.GetNextVertices(i);
            for (int j = 0; j < next.size(); j++)
                list[i].insert(next[j]);
        }
    }
    void AddEdge(int from, int to)
    {
        list[from].insert(to);
    }
    size_t VertexCount() const override
    {
        return list.size();
    }
    TVertexCollection GetNextVertices(int vertex) const override
    {
        TVertexCollection ans;
        for (auto i = list[vertex].begin(); i != list[vertex].end(); ++i)
            ans.push_back(*i);
        return ans;
    }
    TVertexCollection GetPreviousVertices(int vertex) const override
    {
        TVertexCollection ans;
        for (int i = 0; i < list.size(); i++)
        {
            auto got = list[i].find(vertex);
            if (got != list[i].end())
                ans.push_back(i);
        }
        return ans;
    }
private:
    std::vector<std::unordered_set<int>> list;
};

class CArcGraph : public IGraph
{
public:
    CArcGraph() {}
    CArcGraph(CMatrixGraph g)
    {
        int a = g.VertexCount();
        TVertexCollection next;
        for (int i = 0; i < a; i++)
        {
            next = g.GetNextVertices(i);
            for (int j = 0; j < next.size(); j++)
            {
                list.push_back(std::make_pair(i, next[j]));
            }
        }
    }
    CArcGraph(CListGraph g)
    {
        int a = g.VertexCount();
        TVertexCollection next;
        for (int i = 0; i < a; i++)
        {
            next = g.GetNextVertices(i);
            for (int j = 0; j < next.size(); j++)
            {
                list.push_back(std::make_pair(i, next[j]));
            }
        }
    }
    CArcGraph(CSetGraph g)
    {
        int a = g.VertexCount();
        TVertexCollection next;
        for (int i = 0; i < a; i++)
        {
            next = g.GetNextVertices(i);
            for (int j = 0; j < next.size(); j++)
            {
                list.push_back(std::make_pair(i, next[j]));
            }
        }
    }
    void AddEdge(int from, int to) override
    {
        list.push_back(std::make_pair(from, to));
    }

    size_t VertexCount() const override
    {
        int ans = 0;
        for (int i = 0; i < list.size(); i++)
        {
            if (ans < list[i].first)
                ans = list[i].first;
            if (ans < list[i].second)
                ans = list[i].second;
        }
        return ans + 1;
    }

    TVertexCollection GetNextVertices(int vertex) const override
    {
        TVertexCollection ans;
        for (int i = 0; i < list.size(); i++)
        {
            if (list[i].first == vertex)
                ans.push_back(list[i].second);
        }
        return ans;
    }

    TVertexCollection GetPreviousVertices(int vertex) const override
    {
        TVertexCollection ans;
        for (int i = 0; i < list.size(); i++)
        {
            if (list[i].second == vertex)
                ans.push_back(list[i].first);
        }
        return ans;
    }
private:
    std::vector<std::pair<int, int>> list;
};

CListGraph::CListGraph(const CArcGraph &g)
{
    int a = g.VertexCount();
    list.resize(a);
    for (int i = 0; i < a; i++)
    {
        list[i] = g.GetNextVertices(i);
    }
}

CListGraph::CListGraph(const CMatrixGraph &g)
{
    int a = g.VertexCount();
    list.resize(a);
    for (int i = 0; i < a; i++)
    {
        list[i] = g.GetNextVertices(i);
    }
}

CListGraph::CListGraph(const CSetGraph &g)
{
    int a = g.VertexCount();
    list.resize(a);
    for (int i = 0; i < a; i++)
    {
        list[i] = g.GetNextVertices(i);
    }
}


CMatrixGraph::CMatrixGraph(const CArcGraph &g)
{
    int a = g.VertexCount();
    matrix.resize(a, std::vector<int>(a));
    TVertexCollection next;
    for (int i = 0; i < a; i++)
    {
        next = g.GetNextVertices(i);
        for (int j = 0; j < next.size(); j++)
        {
            matrix[i][j] = 1;
        }
    }
}

CMatrixGraph::CMatrixGraph(const CListGraph &g)
{
    int a = g.VertexCount();
    matrix.resize(a, std::vector<int>(a));
    TVertexCollection next;
    for (int i = 0; i < a; i++)
    {
        next = g.GetNextVertices(i);
        for (int j = 0; j < next.size(); j++)
        {
            matrix[i][j] = 1;
        }
    }
}

CMatrixGraph::CMatrixGraph(const CSetGraph &g)
{
    int a = g.VertexCount();
    matrix.resize(a, std::vector<int>(a));
    TVertexCollection next;
    for (int i = 0; i < a; i++)
    {
        next = g.GetNextVertices(i);
        for (int j = 0; j < next.size(); j++)
        {
            matrix[i][j] = 1;
        }
    }
}


CSetGraph::CSetGraph(const CArcGraph &g)
{
    int a = g.VertexCount();
    list.resize(a);
    TVertexCollection next;
    for (int i = 0; i < a; i++)
    {
        next = g.GetNextVertices(i);
        for (int j = 0; j < next.size(); j++)
            list[i].insert(next[j]);
    }
}

CSetGraph::CSetGraph(const CListGraph &g)
{
    int a = g.VertexCount();
    list.resize(a);
    TVertexCollection next;
    for (int i = 0; i < a; i++)
    {
        next = g.GetNextVertices(i);
        for (int j = 0; j < next.size(); j++)
            list[i].insert(next[j]);
    }
}

int main()
{
    int n = 2;
    CListGraph a(n);
    a.AddEdge(0, 1);
    CArcGraph b(a);
    CMatrixGraph c(b);
    CSetGraph d(c);
    return 0;
}