без указателя

#include <iostream>
#include <vector>
#include <cstdlib> // для функций rand() и srand()
#include <list>
using namespace std;

const int p = 2000000033;
const int c = 3;

struct vertex
{
    bool visited = false;
    vector<struct adj_vertex> adj_list;
    int list_size = 0;
    int label = -1;
};

struct adj_vertex
{
    int idx;
    int edge_value;
    int value;
    vertex* to_vertex;
};

class Graph
{
    vertex* vertexes;
    int size;

public:
    Graph(int n);
    int get_size();
    void addEdge(int i, int j, int key);
    void print_graph();
    void DFS(int num_vertex, int value, bool& flag);
    bool is_correct();
};

Graph::Graph(int n)
{
    vertexes = new vertex[n];
    size = n;
}

int Graph::get_size()
{
    return this->size;
}

void Graph::addEdge(int i, int j, int key)
{

    adj_vertex tmp;
    tmp.idx = j;
    tmp.edge_value = key;
    tmp.to_vertex = &vertexes[j];

    vertexes[i].adj_list.push_back(tmp);
    vertexes[i].list_size++;

    tmp.idx = i;
    tmp.to_vertex = &vertexes[i];

    vertexes[j].adj_list.push_back(tmp);
    vertexes[j].list_size++;
}


void Graph::print_graph()
{
    cout << "\n print:" << endl;
    for (int i = 0; i < size; i++)
    {
        cout << "visited = " << vertexes[i].visited << "; i= " << i << "; ";
        cout << " label = " << vertexes[i].label << " : ";
        int size = vertexes[i].adj_list.size();
        cout << "idx =: ";
        for (int j = 0; j < size; ++j)
        {
            cout << vertexes[i].adj_list[j].idx << " ";
        }
        cout << endl;
    }
}

void Graph::DFS(int num_vertex, int value, bool& flag) //мб лучше не по указателю по индексу
{

    if (flag)
    {
        vertexes[num_vertex].visited = true;
        vertexes[num_vertex].label = value;

        vertex u;

        //print_graph();

        for (int i = 0; i < vertexes[num_vertex].list_size; ++i)
        {

                int ind_u = vertexes[num_vertex].adj_list[i].idx;
                u = vertexes[ind_u];
                int rib = vertexes[num_vertex].adj_list[i].edge_value;

                if (!(u.visited))
                {
                    int val = rib - value;
                    DFS(ind_u, val, flag);
                }

                if (vertexes[ind_u].label + vertexes[num_vertex].label != rib)
                {
                    flag = false;
                }

        }
    }
}



bool Graph::is_correct()
{

    print_graph();

    bool flag = true;
    for (int i = 0; i < this->size; ++i)
    {
        if (!vertexes[i].visited)
            DFS(i, 0, flag);
        if (!flag)
            return false;
    }
    return true;
}

int main()
{

    Graph g(4);
    cout << g.get_size();

    g.addEdge(0, 1, 4);
    g.addEdge(1, 2, 5);
    //g.addEdge(0, 2, 3);

    /*
    g.addEdge(0, 1, 5);
    g.addEdge(1, 2, 4);
    g.addEdge(3, 4, 3);
    g.addEdge(5, 6, 5);

    g.addEdge(6, 7, 6);
    g.addEdge(7, 8, 7);
    g.addEdge(7, 11, 3);
    g.addEdge(7, 9, 2);
    g.addEdge(9, 10, 1);

    */

    g.print_graph();

    cout << g.is_correct() << endl;

    return 0;
}