定义什么的就不说了。

Hierholzer 算法求欧拉回路

“逐步插入回路法”。

就是先找到一个回路，然后把回路上一个点替换成一个回路，重复这个操作。

这样暴力做是 $O(m(n+m))$ 的，把找环和 Hierholzer 算法合并可以做 $O(n+m)$

void Hierholzer(int x) {  // 关键函数
  for (int& i = cnt[x]; i < (int)beg[x].size();) {
    if (beg[x][i].exists) {
      edge e = beg[x][i];
      beg[x][i].exists = 0;
      beg[e.to][e.revref].exists = 0;
      ++i;
      Hierholzer(e.to);
    } else {
      ++i;
    }
  }
  ans.push(x);
}

疑问：找边的话，怎么办捏。

欧拉路径编码

一个很巧妙的东西。

求一个字符集为 $m$ 的环，使得环长为 $m^n$，并且环上每 $n$ 个字符得到的字符串各不相同。

做法：以 $m^{n-1}$ 个不同的字符串为点，字符串末尾加入 $m$ 个字符转移到 $m$ 个点，这样就是 $m^{n}$ 条边，找一个欧拉回路，一次把边放在环上。

BEST 引理

先放在这里。