欧拉图与哈密顿图

【欧拉图 - OI Wiki (oi-wiki.org)】

【Problem - 527E - Codeforces】

平面图判定【P3209 [HNOI2010] 平面图判定 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)】

图的联通系数【P5227 [AHOI2013]连通图 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)】

欧拉图

（1）验证欧拉图的方法：

  记录每个点的度数，该图是欧拉图当且仅当所有的点的出入度相等/度数为偶数，同时还要使用并查集判断是否在同一个连通块【连通块这一步需要根据题目灵活判断，因为定义没有硬性规定必须是同一连通块，OI-WIKI上就没有】 

  对了，验证半欧拉图（判断欧拉路径）是有两种情况的：①恰好存在两个度数为奇数的点（出入度差1）②度数都是偶数，别写代码的时候忘了其中一个而怼半天bug。

（2）获取欧拉回路、欧拉路径的方法：

逐步插入回路法-Hierholzer 算法，其流程如下：【复杂度 \(O(n+m)\)，如果对边排序就是多个logn】

• 从起点出发，进行深度优先搜索（起点优先选择奇数的，如果没有，任意一个都可以）。
• 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边，有向图只需要删除单向边，如果是无向图还要删除反边。
• 如果没有可移动的路径，则将所在节点加入到结果中，并返回（这一步就是倒序逐步插入回路，只有倒序插入的边才是欧拉路径上相邻的边）。
• 骑马修栅栏【模板】

当然还有Fleury算法，但是没找到有什么应用的题目。 [有一个Blog写个了不知道对不对的模板]

（3）混合图（有向边+无向边）判断欧拉图（欧拉回路）的方法（网络流）：

　　首先把混合图的所有边随便定向，计算每一个节点的出入度。如果存在某个点的入度、出度的差为奇数，那么就不存在欧拉回路。因为欧拉回路要求在定向后每个点的出入度相等，如果差是奇数，将无法相等。

　　我们记 \(a_i\) 为第 \(i\) 个点的出入度之差 \(\frac{abs(in_i-out_i)}{2}\)。也就是说，对于第 \(i\) 个点，只需要将 \(a_i\) 条边改变方向就可以使得出入度相等。

　　要解决这个问题，我们需要用到网络流模型。首先，有向边是无法改变方向的，所以我们删掉它们再做网络流。网络流要用到的图就是一开始定向的图，我们把边权设定为 \(1\)。然后建一个超级源点 \(s\)、超级汇点 \(t\)，对于 \(in_i>out_i\) 的点，我们连一条 \((i \rightarrow t)\)，边权为\(a_i\)；对于 \(out_i>in_i\) 的点，我们连一条 \((s \rightarrow i)\)，边权为 \(a_i\)。最后跑网络流得到最大流，如果是满流，则说明每个点的要求得到满足，存在欧拉回路，只需要将流量为 \(1\) 的边反向即可。

　　由于是满流，所以每个 \(in_i > out_i\) 的点，都有 \(a_i\) 条边有流量进来，将这些进来的边反向。对于 \(out_i>in_i\) 的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是 \(out_i>in_i\)，和t连接的条件是 \(in_i>out_i\)，那么这个既没和s也没和t连接的点，自然早在开始就已经满足 \(in_i==out_i\) 了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
　　所以，就这样，混合图欧拉回路问题解决了。

哈密顿图

搞两篇理论比较多的文章。

【Ore 条件 - 知乎 (zhihu.com)】

【离散数学笔记（10.2）哈密顿图 - 知乎 (zhihu.com)】

【(80 条消息) 如何理解扩大路径法？ - 知乎 (zhihu.com)】

【】

利用欧拉图解决实际问题：

例题一：无序字母对【欧拉路径】

其实并不需要用并查集判断是否联通，跑一遍dfs，如果有欧拉路径，自然就联通了。

这道题一开始还想不到拿字母建图，一直想拿字符串建，想半天。。。然后发现直接拿字母建就可以了，一个无序对代表双向边，细节就是按字典序最小输出，做法就是先排好序再记录反边。【模板看OI-WIKI】

还有输入字母相同的时候就该特判一下？因为用的是vector存边，真的很烦。

int n, m, du[maxn], cur[maxn], ecnt[maxn];
vector> e;
string st, ans;

inline void dfs(int x) {
  for (int& i = cur[x]; i < e[x].size(); i++) {
    int v = e[x][i].fi, id = e[x][i].se;
    if (v == -1) continue;
    e[x][i].fi = e[v][id].fi = -1;
    dfs(v);
  }
  ans.push_back((char)x);
}

inline void solve() {
  cin >> m, n = 150;
  me(cur, 0), me(du, 0);
  e.assign(n + 1, vector());
  for (int i = 1; i <= m; i++) {
    cin >> st;
    e[st[0]].emp((int)st[1], 0);
    if (st[0] != st[1]) e[st[1]].emp((int)st[0], 0);
    du[st[0]]++, du[st[1]]++;
  }
  int cnt = 0, rt = 0;
  for (int i = 1; i <= n; i++) {
    sort(all(e[i]));
    if (!rt && du[i]) rt = i;
    if (du[i] & 1) {
      if (!(du[rt] & 1) || !rt) rt = i; // 这里也错了好几次。。。
      cnt++;
    }
  }
  if (cnt != 2 && cnt != 0) {
    cout << "No Solution" << endl;
    return;
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0, v; j < e[i].size(); j++) 
      e[i][j].se = ecnt[e[i][j].fi]++; // 重新记录反边
  dfs(rt);
  if (ans.size() < m + 1) { // 判断联通
    cout << "No Solution" << endl;
    return;
  }
  reverse(all(ans));
  cout << ans << endl;
}

例题二：Fair Share【思维 + 建图】

题意：给你m个数组，每个数组一半元素放在 \(multiset\space L\) 里，剩下一半必须放入 \(multiset \space R\) 里，最后让 \(R==L\)。

直接看官方题解就行。

建一个二分图，左侧是数组，右侧是每个数，然后每个数组和数组里面的数连边，跑一个欧拉回路，边的方向从左往右，就放入L里，反之放入R里。

怎么说，关键在于建图。利用了欧拉回路出入度相等的性质，保证了每个数组一半在L，一半在R。

例题三：Date Center Drama【构造 + 贪心思维 + 建图】

题意：给你n个点，m条无向边，让你添加最少的边，使得图上的每个点出入度都是偶数【注意，不是相等】

出入度都是偶数，那么他们的和就是偶数，（然后该题与图联通无关，但是该题的数据好像全是联通的），所以对每个连通块找欧拉回路。

但是具体怎么做呢？

我们先读入无向图，把奇数度的点揪出来（显然只会有偶数个），然后这些点必须连成偶数，最少的方法就是每次找两个奇数点相互连边。

这样每个点度数都是偶数了，我们直接跑欧拉回路，然后这里有点构造的思想。

但是欧拉回路保证的是每个点出入度相等，并没有保证每个点出入度为偶数呀。

我们让欧拉回路相邻的两条边方向不同（相邻指在stack里相邻），这样就保证了（除了起点、终点外的）每个点的出入度都是偶数（这里很关键）。

由于是回路，起点和终点是同一个点，我们最后特判一下这个点是不是偶数，如果不是就多加一个自环。（必须对起点特判）

贪心的证明：

（1）首先加边使得所有的度数成为偶数是必须的，所以这里直接显然不会影响答案。

（2）如果m（m为连通块边数）是奇数（也就是导致起点出入度不为偶数），根据握手定理\(out_{点集}=in_{点集}=m\) ，显然一定会有一个点出入度为奇数，这个时候加一条边是必然的。如果m是偶数，不需要加班。

例题四：破解保险箱【思维 + 建图 + 贪心】

这个题很神奇的结论就是，我们把所有长度为 \(n-1\)的串画出来，每个串有 \(k\)条出边，在这个图上面是有欧拉回路的。这也意味着，我们最短只需要 \(n-1+(n^k)\) 个字母。

难点就在想如何建这个图吧，想到这一步后面都很简单了（虽然建图这一步已经不简单了），毕竟都没让你最小字典序输出。。。

使用k进制优化了一下代码，建议参考。

class Solution {
public:
    unordered_map<int, int> pos;
    int k, K;
    void dfs(const int& cur, string& ans) {
        while(pos[cur] < k) {
            int x = pos[cur]++, nxt = (cur * k + x) % K;
            dfs(nxt, ans);
            ans.push_back('0' + x);
        }
    }
    string crackSafe(int _n, int _k) {
        string R;
        k = _k, K = pow(k, _n - 1);
        dfs(0, R);
        reverse(R.begin(), R.end());
        return string(_n - 1, '0') + R;
    }
};