← all categories

Eulerian Circuit 5074d807

Hierholzer's algorithm for an Eulerian circuit on an undirected multigraph, starting/ending at node 0. adj[u] = {(v, edgeIndex), ...} with both directions of each edge listed (edgeIndex shared by both); mutated in place. Returns {circuit, ok}. For a directed graph: check in-degree == out-degree per node instead of even degree, everything else is the same.

Time: O(V + E). tested

content/graphs/eulerian-circuit.h

pair<vector<int>, bool> eulerianCircuit(int n, int m, vector<vector<pair<int, int>>> &adj) {
    for (int u = 0; u < n; u++) if ((int)adj[u].size() % 2) return {{}, false};

    vector<int> path;
    vector<bool> vis(m);
    auto dfs = [&](auto &&dfs, int u) -> void {
        while (!adj[u].empty()) {
            auto [v, i] = adj[u].back(); adj[u].pop_back();
            if (vis[i]) continue;
            vis[i] = true;
            dfs(dfs, v);
        }
        path.push_back(u);
    };
    dfs(dfs, 0);

    if ((int)path.size() != m + 1) return {{}, false};
    return {path, true};
}