欧拉路径算法

· · 个人记录

欧拉路径，一笔画问题。

判断是否可以一笔画：奇点 0个 或 2个。

需求解一笔画方案。

注意，一笔画方案允许重复经过点，但是每条边必须恰经过一次。

【一个想法】

我们在画一个图形的时候，如果遇到了一个横插进来的图形，我们可以选择从这个点出发画完这个新图形，再回来画完原图形。

【例子】

我们一直往下搜，搜到尽头了就回溯，回溯搜完把退回去的边加进一笔画方案。

举个栗子：

黑色的圈和棕色的圈是我们的原图，标出来的 s 是起点。

当我们遇到了第一个交点，我们选择继续沿着黑圈走。

当我们遇到了第二个交点，我们还是继续沿着黑圈走。

（这就是红线，当然如果你选了其他路也可以）

我们按照红色的路搜，搜回了 s，没路了，开始回溯。

回溯就是绿色线，回到了我们 距离现在最近的 做出选择的 交点，我们发现又可以走了。

接着走，就是蓝色线，我们走了一圈发现又被堵死了。

于是我们再回溯，回溯到 距离现在最近的 做出选择的交点（还是第二个交点），我们发现还是没法走。

但是，我们这还不是最早的交点，再次回溯。

我们终于发现，即便回到了最早的交点，我们依旧走不了。

于是整个搜索结束。

我们按照上面说的流程，用算法手工模拟一遍，得到我们的欧拉路径：

图中橙色的路径就是。

我们再来看一遍算法。

我们从 s 走到第一个交点的一段，是第一层的搜索。

从第一个交点到第二个交点的一段，是第二层的搜索。

从第二个交点又回到 s 的一段，是第三层的搜索。

回到 s，堵住了，于是第三层的搜索结束。

我们在结束之前，把第二个交点到s的这一段，加入了方案。

第三层结束了，我们回溯到第二层。

第二层绕了一圈，堵住了，于是第二层的搜索结束。

我们在结束之前，把棕色圈加入了方案。

第二层结束了，我们回溯到顶层。

顶层直接堵住了，于是顶层的搜索结束。

我们在结束之前，把 s 到第一个交点的这一段，加入了方案。

【具体到实现】

我们梳理了一遍算法执行的流程。

虽然我们可以看到，每层搜索结束时加入的一段路，确实可以组成一条欧拉路径，但是，由于层数高的反而先结束，导致我们加入的顺序和我们实际输出的顺序是完全相反的。

我们先加入的一段，要后输出，这让我们想到一个数据结构：栈。

栈的先进后出，和我们的搜索结束加边，完美地契合了。

于是，我们的流程可以变成这样：

  1. 开始搜索；

  2. 当你搜到了结点 u，遍历 u 的每一条边，往下去搜；

  3. 每当 当前遍历的边 搜完了，把这条边入栈；

  4. 全部搜完之后，从栈顶一路往下输出即可。

注意，这里有几个小细节：

如果是有向图，不必多做处理；但是如果是无向图，我们走了这条边，一样不能再回来。

所以下去之前，不仅要把 我 -> 儿子 的边删掉，还要把 儿子 -> 我 的边，也删掉，这样才避免重复访问。

还有，因为一笔画问题不在乎边权，所以我们存的时候只需要知道有一条边可以走，不需要知道这条边的边权。

所以，当我们用邻接矩阵存，mtr_{i,j} 表示的不是边权，而是 i 到 j 的边的数量。（因为可能重边）

【Code】

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;

int mtr[1005][1005] = {{}};
int ind[1005] = {};

int st[2005], top = 0;

void srh(int x) {
    for (int i = 1; i <= n; i++)
        if (mtr[x][i] > 0) {
            mtr[x][i]--;
            mtr[i][x]--;
            srh(i);
            st[++top] = i;
        }
}

bool chk() {
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (ind[i] % 2 == 1)
            cnt++;
    return cnt <= 2;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        mtr[u][v]++;
        mtr[v][u]++;
        ind[u]++;
        ind[v]++;
    }

    if (!chk()) {
        cout << "No\n";
        return 0;
    }

    srh(1);
    st[++top] = 1;

    if (top != m + 1) {
        cout << "No\n";
        return 0;
    }

    while (top)
        cout << st[top--] << ' ';
    return 0;
}

有向图↓

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>
#include <vector>

using namespace std;
const int N = 100005;

int n, m;
vector<int> e[N];
int cur[N] = {};

int ind[N] = {}, outd[N] = {};

int st[N * 2], top = 0;

int s = 1;

bool chk() {
    int c1 = 0, c2 = 0;
    for (int i = 1; i <= n; i++)
        if (ind[i] == outd[i])
            ;
        else if (ind[i] + 1 == outd[i])
            s = i, c1++;
        else if (outd[i] + 1 == ind[i])
            c2++;
        else
            return false;
    return c1 < 2;
}

void srh(int u) {
    while (cur[u] < e[u].size()) {
        int pos = cur[u]++;
        srh(e[u][pos]);
        st[++top] = e[u][pos];
//      srh(e[u][cur[u]++]);
//      st[++top] = e[u][cur[u] - 1];
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back(v);
        ind[v]++;   
        outd[u]++;
    }

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

    if (!chk()) {
        cout << "No" << endl;
        return 0;
    }

    srh(s);
    st[++top] = s;
    if (top != m + 1)
        cout << "No" << endl;
    else {
        while (top)
            cout << st[top--] << ' ';
        cout << endl;
    }
    return 0;
}