Euler Path and Circuit

1
#include <iostream>
2
#include <vector>
3
#include <stack>
4
#include <algorithm>
5
6
// Undirected Euler path/circuit using Hierholzer's algorithm.
7
// - Works for multigraphs and self-loops
8
// - Checks existence conditions and connectivity (ignoring isolated vertices)
9
10
struct UndirectedEuler {
11
    int n;                                   // number of vertices (0-indexed)
12
    std::vector<std::vector<std::pair<int,int>>> adj; // adj[u] = list of (v, edge_id)
13
    std::vector<int> deg;                    // degree of each vertex
14
    std::vector<int> U, V;                   // endpoints per edge id
15
    std::vector<char> used;                  // used[edge_id]
16
17
    UndirectedEuler(int n): n(n), adj(n), deg(n, 0) {}
18
19
    int add_edge(int u, int v) {
20
        int id = (int)U.size();
21
        U.push_back(u); V.push_back(v);
22
        if ((int)used.size() <= id) used.resize(id + 1, 0);
23
        adj[u].push_back({v, id});
24
        adj[v].push_back({u, id});
25
        if (u == v) {
26
            // self-loop contributes 2 to degree
27
            deg[u] += 2;
28
        } else {
29
            deg[u]++; deg[v]++;
30
        }
31
        return id;
32
    }
33
34
    // Check connectivity on the subgraph induced by vertices with deg > 0
35
    bool connected_ignoring_isolates(int start) {
36
        if (start == -1) return true; // no edges at all
37
        std::vector<char> vis(n, 0);
38
        std::stack<int> st; st.push(start); vis[start] = 1;
39
        while (!st.empty()) {
40
            int u = st.top(); st.pop();
41
            for (auto [v, id] : adj[u]) {
42
                if (!vis[v]) { vis[v] = 1; st.push(v); }
43
            }
44
        }
45
        for (int v = 0; v < n; ++v) if (deg[v] > 0 && !vis[v]) return false;
46
        return true;
47
    }
48
49
    // Returns empty vector if no Euler trail exists.
50
    // Otherwise returns the vertex sequence (size = E + 1).
51
    std::vector<int> euler_trail_or_circuit() {
52
        int E = (int)U.size();
53
        used.assign(E, 0);
54
55
        // Pick start vertex based on odd-degree count
56
        std::vector<int> odd;
57
        for (int v = 0; v < n; ++v) if (deg[v] % 2 == 1) odd.push_back(v);
58
        if (!(odd.size() == 0 || odd.size() == 2)) return {}; // necessary condition fails
59
60
        int start = -1;
61
        if (odd.size() == 2) start = odd[0];
62
        else {
63
            for (int v = 0; v < n; ++v) if (deg[v] > 0) { start = v; break; }
64
        }
65
        if (!connected_ignoring_isolates(start)) return {};
66
        if (start == -1) return {0}; // Graph with no edges; define trivial path
67
68
        std::vector<int> it(n, 0);          // next index to scan per vertex
69
        std::vector<int> out; out.reserve(E + 1);
70
        std::stack<int> st; st.push(start);
71
72
        while (!st.empty()) {
73
            int u = st.top();
74
            // advance iterator to the next unused edge
75
            while (it[u] < (int)adj[u].size() && used[ adj[u][it[u]].second ]) it[u]++;
76
            if (it[u] == (int)adj[u].size()) {
77
                // no more edges from u: add to path
78
                out.push_back(u);
79
                st.pop();
80
            } else {
81
                auto [v, id] = adj[u][it[u]++];
82
                if (used[id]) continue; // skip already used (seen from the other side)
83
                used[id] = 1;
84
                st.push(v);
85
            }
86
        }
87
        if ((int)out.size() != E + 1) return {}; // not all edges were used
88
        std::reverse(out.begin(), out.end());
89
        return out;
90
    }
91
};
92
93
int main() {
94
    // Example: undirected graph with an Euler path
95
    // 0-1-2-0 and 1-3 (odd vertices are 1 and 3)
96
    UndirectedEuler G(4);
97
    G.add_edge(0,1);
98
    G.add_edge(1,2);
99
    G.add_edge(2,0);
100
    G.add_edge(1,3);
101
102
    auto trail = G.euler_trail_or_circuit();
103
    if (trail.empty()) {
104
        std::cout << "No Euler trail\n";
105
    } else {
106
        std::cout << "Euler trail (vertices): ";
107
        for (size_t i = 0; i < trail.size(); ++i) {
108
            if (i) std::cout << ' ';
109
            std::cout << trail[i];
110
        }
111
        std::cout << "\nLength (edges) = " << (int)trail.size() - 1 << "\n";
112
    }
113
    return 0;
114
}
115

1
#include <iostream>
2
#include <vector>
3
#include <stack>
4
#include <algorithm>
5
6
struct DirectedEuler {
7
    int n;
8
    std::vector<std::vector<std::pair<int,int>>> adj; // adj[u] = (v, id)
9
    std::vector<int> indeg, outdeg;
10
    std::vector<int> U, V; // edges u->v
11
    std::vector<char> used;
12
13
    DirectedEuler(int n): n(n), adj(n), indeg(n,0), outdeg(n,0) {}
14
15
    int add_edge(int u, int v) {
16
        int id = (int)U.size();
17
        U.push_back(u); V.push_back(v);
18
        if ((int)used.size() <= id) used.resize(id + 1, 0);
19
        adj[u].push_back({v, id});
20
        outdeg[u]++; indeg[v]++;
21
        return id;
22
    }
23
24
    // Weak connectivity on vertices with nonzero degree (ignore directions)
25
    bool weakly_connected_ignoring_isolates(int start) {
26
        if (start == -1) return true; // no edges
27
        std::vector<char> vis(n, 0);
28
        std::stack<int> st; st.push(start); vis[start] = 1;
29
        while (!st.empty()) {
30
            int u = st.top(); st.pop();
31
            // traverse outgoing
32
            for (auto [v, id] : adj[u]) if (!vis[v]) { vis[v]=1; st.push(v); }
33
            // traverse incoming by scanning all edges (build reverse view on the fly)
34
            for (int v = 0; v < n; ++v) {
35
                // Cheap but O(VE) if used naively; instead, we can rely on an auxiliary undirected adjacency.
36
            }
37
        }
38
        // The loop above is inefficient; build an undirected adjacency once instead:
39
        return false;
40
    }
41
42
    // Build weak connectivity using an auxiliary undirected adjacency (efficient)
43
    bool weakly_connected() {
44
        int start = -1;
45
        std::vector<std::vector<int>> und(n);
46
        for (size_t i = 0; i < U.size(); ++i) {
47
            int a = U[i], b = V[i];
48
            und[a].push_back(b);
49
            und[b].push_back(a);
50
        }
51
        for (int v = 0; v < n; ++v) if (indeg[v] + outdeg[v] > 0) { start = v; break; }
52
        if (start == -1) return true; // no edges
53
        std::vector<char> vis(n, 0);
54
        std::stack<int> st; st.push(start); vis[start] = 1;
55
        while (!st.empty()) {
56
            int u = st.top(); st.pop();
57
            for (int w : und[u]) if (!vis[w]) { vis[w]=1; st.push(w); }
58
        }
59
        for (int v = 0; v < n; ++v) if ((indeg[v] + outdeg[v] > 0) && !vis[v]) return false;
60
        return true;
61
    }
62
63
    // Returns empty if no Euler trail exists; otherwise vertex sequence of size E+1
64
    std::vector<int> euler_trail_or_circuit() {
65
        int E = (int)U.size();
66
        used.assign(E, 0);
67
68
        if (!weakly_connected()) return {};
69
70
        int start = -1, end = -1;
71
        for (int v = 0; v < n; ++v) {
72
            int diff = outdeg[v] - indeg[v];
73
            if (diff == 1) {
74
                if (start == -1) start = v; else return {};
75
            } else if (diff == -1) {
76
                if (end == -1) end = v; else return {};
77
            } else if (diff != 0) {
78
                return {}; // imbalance too large
79
            }
80
        }
81
        if (start == -1) {
82
            // Euler circuit case: start at any vertex with outdeg > 0
83
            for (int v = 0; v < n; ++v) if (outdeg[v] > 0) { start = v; break; }
84
        }
85
        if (start == -1) return {0}; // empty graph: trivial path
86
87
        std::vector<int> it(n, 0), out;
88
        out.reserve(E + 1);
89
        std::stack<int> st; st.push(start);
90
91
        while (!st.empty()) {
92
            int u = st.top();
93
            while (it[u] < (int)adj[u].size() && used[ adj[u][it[u]].second ]) it[u]++;
94
            if (it[u] == (int)adj[u].size()) {
95
                out.push_back(u);
96
                st.pop();
97
            } else {
98
                auto [v, id] = adj[u][it[u]++];
99
                if (used[id]) continue;
100
                used[id] = 1;
101
                st.push(v);
102
            }
103
        }
104
        if ((int)out.size() != E + 1) return {};
105
        std::reverse(out.begin(), out.end());
106
        return out;
107
    }
108
};
109
110
int main() {
111
    // Example: directed Euler circuit
112
    // 0->1->2->0 and 0->3->1 (balances maintained)
113
    DirectedEuler G(4);
114
    G.add_edge(0,1);
115
    G.add_edge(1,2);
116
    G.add_edge(2,0);
117
    G.add_edge(0,3);
118
    G.add_edge(3,1);
119
120
    auto path = G.euler_trail_or_circuit();
121
    if (path.empty()) {
122
        std::cout << "No directed Euler trail\n";
123
    } else {
124
        std::cout << "Directed Euler trail (vertices): ";
125
        for (size_t i = 0; i < path.size(); ++i) {
126
            if (i) std::cout << ' ';
127
            std::cout << path[i];
128
        }
129
        std::cout << "\nLength (edges) = " << (int)path.size() - 1 << "\n";
130
    }
131
    return 0;
132
}
133

1
#include <iostream>
2
#include <vector>
3
#include <set>
4
#include <algorithm>
5
6
// Compute lexicographically smallest Euler trail/circuit by always taking the smallest neighbor.
7
// Uses multiset adjacency; supports parallel edges and self-loops.
8
9
struct LexiEuler {
10
    int n;
11
    std::vector<std::multiset<int>> adj; // undirected multigraph
12
    std::vector<int> deg;
13
14
    LexiEuler(int n): n(n), adj(n), deg(n,0) {}
15
16
    void add_edge(int u, int v) {
17
        adj[u].insert(v);
18
        adj[v].insert(u);
19
        if (u == v) deg[u] += 2; else { deg[u]++; deg[v]++; }
20
    }
21
22
    bool connected_ignoring_isolates(int start) {
23
        if (start == -1) return true;
24
        std::vector<char> vis(n, 0);
25
        std::vector<int> st = {start}; vis[start] = 1;
26
        for (size_t i = 0; i < st.size(); ++i) {
27
            int u = st[i];
28
            for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; st.push_back(v); }
29
        }
30
        for (int v = 0; v < n; ++v) if (deg[v] > 0 && !vis[v]) return false;
31
        return true;
32
    }
33
34
    void dfs(int u, std::vector<int>& out) {
35
        while (!adj[u].empty()) {
36
            int v = *adj[u].begin(); // smallest neighbor
37
            // remove one copy from both sides
38
            adj[u].erase(adj[u].begin());
39
            auto it = adj[v].find(u);
40
            if (it == adj[v].end()) {
41
                // should not happen in a well-formed undirected multigraph
42
                continue;
43
            }
44
            adj[v].erase(it);
45
            dfs(v, out);
46
        }
47
        out.push_back(u);
48
    }
49
50
    std::vector<int> smallest_euler() {
51
        std::vector<int> odd;
52
        for (int v = 0; v < n; ++v) if (deg[v] % 2 == 1) odd.push_back(v);
53
        if (!(odd.size() == 0 || odd.size() == 2)) return {};
54
        int start = -1;
55
        if (!odd.empty()) start = *std::min_element(odd.begin(), odd.end());
56
        else {
57
            for (int v = 0; v < n; ++v) if (deg[v] > 0) { start = v; break; }
58
        }
59
        if (!connected_ignoring_isolates(start)) return {};
60
        if (start == -1) return {0}; // no edges
61
        std::vector<int> out;
62
        dfs(start, out);
63
        std::reverse(out.begin(), out.end());
64
        // verify all edges used: sum deg / 2 edges implies out.size() == E + 1
65
        long long E = 0; for (int d : deg) E += d; E /= 2;
66
        if ((int)out.size() != (int)E + 1) return {}; // not all edges covered
67
        return out;
68
    }
69
};
70
71
int main() {
72
    // Example that demonstrates lexicographically smallest trail
73
    // Graph: 0-1 (x2 parallel), 0-2, 1-2, 1-3
74
    LexiEuler G(4);
75
    G.add_edge(0,1);
76
    G.add_edge(0,1); // parallel edge
77
    G.add_edge(0,2);
78
    G.add_edge(1,2);
79
    G.add_edge(1,3);
80
81
    auto trail = G.smallest_euler();
82
    if (trail.empty()) {
83
        std::cout << "No Euler trail\n";
84
    } else {
85
        std::cout << "Lexicographically smallest Euler trail: ";
86
        for (size_t i = 0; i < trail.size(); ++i) {
87
            if (i) std::cout << ' ';
88
            std::cout << trail[i];
89
        }
90
        std::cout << '\n';
91
    }
92
    return 0;
93
}
94