欧拉路/欧拉回路

欧拉路/欧拉回路简介

经过图中所有边恰好一次的通路称为欧拉通路或欧拉路。

经过图中所有边恰好一次的回路称为欧拉回路。

判别法

对于无向图G，G中存在欧拉回路当且仅当G中所有度非0的点是连通的且没有奇数度数的点。

对于无向图G，G中存在欧拉路当且仅当G中所有非0的点是连通的且G中恰有0或2个奇数度数的点（0个表示存在欧拉回路）。

对于有向图G，G中存在欧拉回路当且仅当G中所有度非0的点是强连通的且每个点的入度和出度相同。

对于有向图G，G中存在欧拉路当且仅当：

将G中所有有向边改为无向边后，G中所有度非0的点是连通的；

最多只有一个点的出度减去入度为1；

最多只有一个点的入度减去出度为1；

其他所有点的入度等于出度。

流程

先判断图中是否存在欧拉图（检查非0的点的连通性及度数）

然后采用dfs来构造求解欧拉路

令P为最终的路径序列，记路径起点为x（如果无向图全为偶数度数的点则随便找一个度数非0的点为x，否则找2个奇数点中任意一个为x；如果有向图所有点入度等于出度则随便找一个为x，否则找出度减入度为1的点为x）；

dfs(node u)：

遍历所有u连出去的边u→v，且u→v之前没有被访问过；

将边u→v打上标记（如果是无向图则v→u也要打上标记）；

dfs(v)；

将边u→v添加到路径序列P中；

dfs(x)结束后，将P中记录的边倒序输出，即为求得的欧拉路、

时间复杂度：$O(n+m)$（找起点$O(n)$，找欧拉路$O(m)$）

有向图（有连通性保证）

vector<int> edge[N];
int n, m, l, f[N], ind[N], outd[N], c[M];
inline void dfs(int x)
{
    while (f[x] < outd[x])
    {
        int y = edge[x][f[x]];
        f[x]++;
        dfs(y);
        c[++l] = y;
    }
}
inline void Euler()
{
    int x = 0, y = 0, z = 0; // x:起点,y:出度比入度大1,z:出度不等于入度的点
    for (int i = 1; i <= n; i++)
    {
        if (ind[i] + 1 == outd[i])
            x = i, ++y;
        if (ind[i] != outd[i])
            ++z;
    }
    if (!((y == 1 && z == 2) || !z))
    {
        printf("No\n");
        return;
    }
    if (!x)
        for (int i = 1; i <= n; i++)
            if (ind[i])
                x = i;
    memset(f, 0, sizeof f);
    l = 0;
    dfs(x);
    c[++l] = x;
    if (l == m + 1)
        printf("Yes\n");
    else
    {
        printf("No\n");
        return;
    }
    for (int i = l; i; --i)
        printf("%d ", c[i]);
}

无向图（不保证连通性）

struct Node
{
    int y, idx;
    Node(int _y, int _idx)
    {
        y = _y;
        idx = _idx;
    }
};
vector<Node> edge[N];
int n, m, l, cnt = 1, f[N], d[N], c[M];
bool b[2 * M];
inline void dfs(int x)
{
    while (f[x] < d[x])
    {
        int y = edge[x][f[x]].y, idx = edge[x][f[x]].idx;
        if (!b[idx])
        {
            f[x]++;
            b[idx] = b[idx ^ 1] = true;
            dfs(y);
            c[++l] = y;
        }
        else
            f[x]++;
    }
}
inline void Euler()
{
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++)
        if (d[i] & 1)
            x = i, ++y;
    if (y && y != 2)
    {
        printf("No\n");
        return;
    }
    if (!x)
        for (int i = 1; i <= n; i++)
            if (d[i])
                x = i;
    memset(f, 0, sizeof f);
    memset(b, false, sizeof b);
    l = 0;
    dfs(x);
    c[++l] = x;
    if (l != m + 1)
    {
        printf("No\n");
        return;
    }
    printf("Yes\n");
     for (int i = l; i; --i)
        printf("%d ", c[i]);
}