AlgorithmLibrary/EulerPath.cpp at master · bluecoffee8/AlgorithmLibrary · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
/**
 * Author: Kevin Li
 * Lang: C++
 * Description: finds Euler tour
 */

#include <iostream>
#include <vector>
#include <list>
#include <unordered_map>
using namespace std;
#define INF 1000000000
#define pb push_back
#define mp make_pair
#define f first
#define s second
typedef pair<int,int> pi;

struct eulerian {
    struct ph {
        size_t operator () (const pi&a) const {
            return INF*a.first + a.second;
        }
    };
    int n;
    vector<int> *e;
    int *deg;
    list<int> cycle;
    unordered_map<pi,bool,ph> vis;
    eulerian () {}
    eulerian (int _n) : n(_n) {
        e = new vector<int>[n];
        deg = new int[n];
        for (int i = 0; i < n; i++) deg[i] = 0;
        dvis = new bool[n];
    }
    void add(int u, int v) {
        e[u].pb(v);
        e[v].pb(u);
        deg[u]++;
        deg[v]++;
        vis[mp(u,v)] = false;
        vis[mp(v,u)] = false;
    }
    bool *dvis;
    int vc;
    void cdfs(int node) {
        dvis[node] = true;
        vc++;
        for (int i = 0; i < e[node].size(); i++) {
            if (!dvis[e[node][i]]) {
                cdfs(e[node][i]);
            }
        }
    }
    bool connected() {
        vc = 0;
        for (int i = 0; i < n; i++) {
            dvis[i] = false;
        }
        cdfs(0);
        return (vc == n);
    }
    bool exist() {
        if (!connected()) return false;
        for (int i = 0; i < n; i++) {
            if (deg[i]%2) {
                return false;
            }
        }
        return true;
    }
    void dfs(list<int>::iterator itr, int node) {
        for (int i = 0; i < e[node].size(); i++) {
            if (!vis[mp(node,e[node][i])]) {
                vis[mp(node,e[node][i])] = true;
                vis[mp(e[node][i],node)] = true;
                dfs(cycle.insert(itr,node),e[node][i]);
            }
        }
    }
    void driver(int start) {
        dfs(cycle.begin(),start);
    }
    void print() {
        for (auto i = cycle.begin(); i != cycle.end(); i++) {
            cout << *i << " ";
        }
        cout << *(cycle.begin()) << " ";
        cout << endl;
    }
};

int n,m,start;

int main() {
    cin >> n >> m >> start;
    eulerian E = eulerian(n);
    for (int i = 0; i < m; i++) {
        int u,v; cin >> u >> v;
        E.add(u,v);
    }
    if (E.exist()) {
        E.driver(start);
        E.print();
    }
}