欧拉回路 | 梦始

欧拉回路是这样一个东西（个人理解）：从图上某个点出发，每条边不能重复经过，然后从这个点开始把所有的点和边走一遍（同时满足每条边不能重复）后回到这个点。

怎么求？一种办法是Fluery , 即每次只找不是桥的边bfs，当每个点和边都进队后再处理桥，如果图不连通或者经过桥之后无法遍历整个图，则没有欧拉回路，否则就找到了欧拉回路，由于这样实现需要先tarjan缩强连通分量后记录桥的位置，之后再每个点遍历，需要时间复杂度大约是O(n ^ 2), 太不牛，我们换下一个算法

Hierholzer算法

（不是这什么鬼名字也太长……）
我直接把函数名字写成dfs了，板子如下（自己实现的用起来自己舒服）

vector<int> now(n + 1);
stack<int> s;
auto dfs = [&](auto self, int u) -> void {
    for (int i = now[u]; i < e[u].size(); i = now[u]) {
        now[u]++;
        self(self, e[u][i]);
    }
    s.push(u);
};

首先说一下有向图欧拉通路的判定：（需要满足以下2 之一）

所有顶点出度等于入度
有且只有一个顶点出度等于入度加一，同时有另外一个顶点入度等于出度加一（可以想象成每个顶点2个2个删边之后会剩下一条，而这条路如果一开始就走也可以形成欧拉回路）

接下来解释一下上面实现：
now数组记录经过当前顶点次数（每次走过后让路径穿过这个点，之后继续dfs下一个点），回来的时候记录，由于是逆序的，所以开了个stack

next is the code of P7771 [洛谷P7771] : https://www.luogu.com.cn/problem/P7771

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> e(n + 1);
    vector<int> in(n + 1), out(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        e[u].push_back(v);
        in[v]++;
        out[u]++;
    }

    int vis1 = 0, vis2 = 0;
    for (int i = 1; i <= n; i++) {
        if (in[i] == out[i]) continue;
        if (in[i] == out[i] + 1) {
            if (!vis1) vis1 = i;
            else {
                cout << "No\n";
                return 0;
            }
            continue;
        }
        if (in[i] == out[i] - 1) {
            if (!vis2) vis2 = i;
            else {
                cout << "No\n";
                return 0;
            }
            continue;
        }
        cout << "No\n";
        return 0;
    }

    vector<int> now(n + 1);
    stack<int> s;
    auto dfs = [&](auto self, int u) -> void {
        for (int i = now[u]; i < e[u].size(); i = now[u]) {
            now[u]++;
            self(self, e[u][i]);
        }
        s.push(u);
    };

    for (int i = 1; i <= n; i++) {
        sort(e[i].begin(), e[i].end());
    }

    if (vis2) dfs(dfs, vis2);
    else {
        dfs(dfs, 1);
    }

    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    cout << '\n';
    return 0;
}

应用例子:
洛谷P1341 字符串匹配，以前cf有一道传送门的题，好像是某场div3 E题也是一模一样：
思路，想要拿到一个首尾相链接的串，则直接跑一边欧拉回路（就好像每个字符串就是一个节点，每个相同的字符就是一个传送门，那么对于相同的字符就建边链接，同时统计每个点的度数，由于欧拉通路判定需要满足以下两个条件之一 :

所有点都是偶数度

有奇数度顶点且奇数度顶点有且只有2个
在接下来判定时就可以直接使用记录的度数。
之后就跑一遍欧拉回路，记录路径，输出路径，一遍AC!!!

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int inf = 1e9 + 7;

void solve() {
    int n;
    cin >> n;

    int start = inf;
    vector<vector<int>> e(59, vector<int>(59, 0));
    vector<int> du(59);
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        int u = s[0] - 'A';
        int v = s[1] - 'A';

        start = min({start, u, v});
        e[u][v] = e[v][u] = 1;
        du[u]++;
        du[v]++; 
    }

    int cnt = 0;
    int pos = -1;
    for (int i = 0; i < 58; i++) {
        if (du[i] & 1) {
            if (pos == -1) pos = i;
            cnt++;
        } 
    }

    stack<int> s;
    vector<int> now(n + 1);
    auto dfs = [&](auto self, int u) -> void {
        for (int i = 0; i < 58; i++) {
            if (e[u][i]) {
                e[u][i] = e[i][u] = 0;
                self(self, i);
            }
        }
        s.push(u);
    };

    //cerr << (char)(start + 'A')<< '\n';
    if (cnt == 0) dfs(dfs, start);
    else if (cnt == 2) dfs(dfs, pos);
    else {
        cout << "No Solution\n";
        return;
    }
    
    while (!s.empty()) {
        char c = (char)(s.top() + 'A');
        cout << c;
        s.pop();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}