Граф

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

struct pr {
    int x;
    bool marked = false;
    pr(int i) {
        x = i;
    }
};

typedef pr Pair;

struct node {
    int i = NULL;
    vector <int> edges;
    node* nextVertex;
    node(int n) {
        i = n;
        nextVertex = NULL;
    }
};

typedef node Node;

class Graph {
    Node* head;
    deque<Pair> visited;
    int N;
public:
    Graph(int t){
        this->N = t;
    }
    void addEdge(int, int, bool);
    void addVertex(int);
    node* existVertex(int);
    void print();
    bool eiler();
    void get_tree();
    node* nextUp(node* i);
};

node* Graph::existVertex(int i) {
    node* cur = this->head;
    while (cur != NULL) {
        if (cur->i == i) {
            return cur;
            break;
        }
        cur = cur->nextVertex;
    }
    return 0;
}

void Graph::addEdge(int i, int j, bool status) {
    if (this->head == NULL) {
        this->head = new node(i);
        this->head->edges.push_back(j);
        node* cur = this->head;
        if (status == true) {
            cur->nextVertex = new node(j);
            cur->nextVertex->edges.push_back(i);
        }
    }
    else if (existVertex(i) != NULL) {
        node* cur = existVertex(i);
        cur->edges.push_back(j);
        if (existVertex(j) == NULL) {
            while (cur->nextVertex != NULL) cur = cur->nextVertex;
            cur->nextVertex = new node(j);
        }
        if (status == true) {
            cur->nextVertex->edges.push_back(i);
        }
    }
    else {
        node* cur = this->head;
        while (cur->nextVertex != NULL) cur = cur->nextVertex;
        cur->nextVertex = new node(i); //cur->nextVertex->edges.push_back(pr(j,w));
        if (existVertex(j) == NULL) {
            cur->nextVertex = new node(j);
        }
        else {
            node* buf = this->head; while (buf->i != j) buf = buf->nextVertex;
            buf->edges.push_back(i);
        }
        if (status == true) {
            cur->nextVertex->edges.push_back(j);
        }
    }
}

void Graph::addVertex(int i) {
    if (existVertex(i) == NULL) {
        node* cur = this->head;
        while (cur->nextVertex != NULL) cur = cur->nextVertex;
        cur->nextVertex = new node(i);
    }
}

void Graph::print() {
    node* cur = this->head;
    while (cur != NULL) {
        std::cout << cur->i << " -> ";
        if (cur->edges.size() == 1) {
            printf("%d", *cur->edges.begin());
        }
        else {
            auto it = cur->edges.begin();
            auto end = cur->edges.end();
            while (it != end) {
                printf("%d ", *it);
                it++;
            }
        }
        cur = cur->nextVertex;
        printf("\n");
    }
}

bool Graph::eiler() {
    node* cur = this->head;
    int count = 0;
    while (cur != NULL) {
        if (cur->edges.size() != 0) {
            if (cur->edges.size() % 2 == 1) count++;
        }
        cur = cur->nextVertex;
    }
    if (count > 2) return false;
    else return true;
}

node* Graph::nextUp(node* i) {
    node* buff = i; node* b = this->head;
    for (int i = 0; i < this->visited.size(); i++) {
        if (visited[i].x == buff->i) {
            this->visited[i].marked = true;
            //if (buff->edges.size() > 2) this->visited[i].marked = false;
            break;
        }
    }
    cout <<  " -> " << buff->i;
    for (int i = 0; i < buff->edges.size(); i++) {
        while (b->i != buff->edges.at(i)) b = b->nextVertex;
        for (int i = 0; i < visited.size(); i++) {
            if (visited[i].x == b->i && visited[i].marked == false) return nextUp(b);
        }
    }
}

void Graph::get_tree() {
    node* cur = this->head;
    while (cur != NULL) {
        visited.push_back(pr(cur->i));
        cur = cur->nextVertex;
    }
    cur = this->head;
    nextUp(cur);
    for (int i = 0; i < visited.size(); i++) {
        if (visited[i].marked == false) {
            cur = this->head;
            this->visited[i].marked = true;
            while (cur->i != visited[i].x) cur = cur->nextVertex;
            cout << " -> " << cur->edges.at(0);
            nextUp(cur);
        }
    }
}

int main() {
    setlocale(0, "");
    Graph G(10); int i = 0, j = 0;
    cout << "\nЧтобы добавить ребро, введите 1.\nЧтобы вывести граф, введите 2.\nЧтобы определить эйлеров цикл, нажмите 3.\nЧтобы найти эйлеров путь, нажмите 4.\n";
    int n = -1; int s = 0; node* tmp;
    node* tree = NULL;
    while (n != 0) {
        cin >> n;
        switch (n) {
        case 1:
            cin >> i; cin >> j;
            G.addEdge(i, j, true);
            i = 0, j = 0;
            break;
        case 2:
            G.print();
            printf("\n");
            break;
        case 3:
            cout << "Граф эйлеров? ->" << G.eiler() << endl;
            break;
        case 4:
            G.get_tree();
            break;
        }
    }
    return 0;
}