Eulerian Path

An Eulerian path (欧拉路径; 一笔画问题) is a path visiting every edge exactly once.

Any connected directed graph where all nodes have equal in-degree and out-degree has an Eulerian circuit (an Eulerian path ending where it started.)

If the end point is the same as the starting point, this Eulerian Path is called an Eulerian Circuit (欧拉回路).

Detecting Eulerian Path

Undirected Graph:

• If there are only TWO nodes with odd degrees and all other nodes have even degrees, then there must exist an Eulerian Path (NOT Circuit) from one of the odd-degree node to the other odd-degree node.

• If all nodes have even degrees, this Eulerian Path is also a Eulerian Circuit.

Directioned Graph:

• If there is at most one node u whose outdegree[u] = indegree[u] + 1, and at most one node v whose indegree[v] = outdegree[v] + 1, then there must exists an Eulerian Path from u (If u doesn't exist, any node works) to v (If v doesn't exist, any node works).

• If every nodes n has indegree[n] = outdegree[n], then there is an Eulerian Circuit.

Finding Eulerian Circuit: Hierholzer’s Algorithm

Hierholzer’s Algorithm for directed graph

We can find the circuit/path in O(E), i.e. linear time.

The algorithem is as follows (wiki):

• Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.

• As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.

• Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph.

This is a Post-order DFS.

The following code is for 2097. Valid Arrangement of Pairs (Hard)

// OJ: https://leetcode.com/problems/valid-arrangement-of-pairs/
// Author: github.com/lzl124631x
// Time: O(N + U) where N is the number of pairs and U is the number of unique numbers in the pairs
// Space: O(N + U)
class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& E) {
        int N = E.size();
        unordered_map<int, vector<int>> G;
        unordered_map<int, int> indegree, outdegree;
        G.reserve(N);
        indegree.reserve(N);
        outdegree.reserve(N);
        for (auto &e : E) {
            int u = e[0], v = e[1];
            outdegree[u]++;
            indegree[v]++;
            G[u].push_back(v);
        }
        int start = -1;
        for (auto &[u, vs] : G) {
            if (outdegree[u] - indegree[u] == 1) {
                start = u; // If there exists one node `u` that `outdegree[u] = indegree[u] + 1`, use `u` as the start node.
                break;
            }
        }
        if (start == -1) start = E[0][0]; // If there doesn't exist such node `u`, use any node as the start node
        vector<vector<int>> ans;
        function<void(int)> euler = [&](int u) {
            auto &vs = G[u];
            while (vs.size()) {
                int v = vs.back();
                vs.pop_back();
                euler(v);
                ans.push_back({ u, v }); // Post-order DFS. The edge is added after node `v` is exhausted
            }
        };
        euler(start);
        reverse(begin(ans), end(ans)); // Need to reverse the answer array in the end.
        return ans;
    }
};

Problems

• 332. Reconstruct Itinerary (Hard)
• 753. Cracking the Safe (Hard)
• 2097. Valid Arrangement of Pairs (Hard)