Discrete Mathematics. Laboratory work №7.

gistfile1.cpp

#include <vector>
#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

vector< vector<int> > g, gm;
vector< int > cc;
vector< int> ans;

void findEulerPath(int v) {
    while(g[v].size() > 0) {
        int to = g[v].back();
        g[v].pop_back();
        findEulerPath(to);
    }
    ans.push_back(v);
}

bool findGamilton(int start, int current, vector<int>& ans, vector<bool>& visited, bool& path, bool& cycle, int remains) {
    visited[current] = true;
    ans.push_back(current);

    if(remains == 1 && gm[current][start]) {
        cycle = true;
        return true;
    } else if(remains == 1 && !gm[current][start]) {
        path = true;
        return true;
    }

    for(int i = 0; i < gm.size(); i++) {
        if(!visited[i] && gm[current][i]) {
            if(findGamilton(start, i, ans, visited, path, cycle, remains - 1))
                return true;
        }
    }

    visited[current]  = false;
    ans.pop_back();
    return false;
}

int main() {
  //  freopen("/home/acarus/input.txt", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);

    g.assign(n, vector<int>());
    gm.assign(n, vector<int>(n, 0));
    cc.assign(n, 0);

    int a, b;
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        a--, b--;
        g[a].push_back(b);
        gm[a][b] = 1;
        cc[a]--;
        cc[b]++;
    }

    int numberOfOdd = 0;
    int OddVertex = -1;
    for(int i = 0; i < n; i++)
        if(cc[i] != 0) {
            numberOfOdd++;
            if(cc[i] < 0)
                OddVertex = i;
        }

    if(numberOfOdd != 0 && numberOfOdd != 2) {
        // graph is not Eulerian
        printf("graph is not Eulerian\r\n");
    } else if(numberOfOdd == 2) {
        // we have Eulerian path
        printf("We have Eulerian path\n");
        findEulerPath(OddVertex);
        reverse(ans.begin(), ans.end());
        for(int x: ans)
            printf("%d ", x + 1);
        printf("\n");
    } else if(numberOfOdd == 0) {
        // we have Eulerian cycle
        printf("We have Eulerian cycle\n");
        findEulerPath(a);
        reverse(ans.begin(), ans.end());
        for(int x: ans)
            printf("%d ", x + 1);
        printf("\n");
    }

    // Gamilton cycle and path
    vector<int> ans;
    vector<bool> visited(n, false);
    bool path = false;
    bool cycle = false;

    for(int i = 0; i < n; i++) {
        path = cycle = false;
        visited.assign(n, false);
        findGamilton(i, i, ans, visited, path, cycle, n);
        if(path || cycle) {
            break;
        }

    }

   if(cycle) {
        printf("We have Gamilton cycle\n");
   } else if(path) {
        printf("We have Gamilton path\n");
   } else if(!cycle && !path){
        printf("It is not Hamiltonian Graph\n");
   }

   if(cycle || path) {
        for(int x: ans)
            printf("%d ", x + 1);
        printf("\n");
   }

//    system("python /home/acarus/edu/discrete/GraphDrawer/draw.py /home/acarus/input.txt res.png");
//    system("xdg-open res.png");
    return 0;
}