欧拉路径与欧拉回路

充分条件和必要条件(充要条件就是两个都有啦)

若a能推出b则称a是b的充分条件

若b存在一定就有a, 称b是a的必要条件

无向图的欧拉路径

$•$ 定义: 在一张无向图中, 若点a出发到达点b, 路径上每条边只经过1次, 则称a到b的这条路径为一条欧拉路径

$•$ 无向图欧拉路径存在的充要条件: 度数为奇数的点的个数是0个或2个.

$•$ 无向图的欧拉回路(欧拉环):一条起点和终点重叠的欧拉路径

$•$ 无向图欧拉路径的实现 时间复杂度 $O(n+m)$

1. 统计每个点的度数d[i]

2. 判断是否无解;

3. 在有解的前提下, 写一个从度数为奇数的点(若没有随便选一个点)出发dfs;

4. 维护一个栈s, 在dfs时将遍历的点存入栈中

5. 最后输出s的节点编号即为一条欧拉路径;

欧拉路径题目的坑点

1. 重边

2. 欧拉路径和欧拉回路

3. 字典序

4. 特判无解

模板题 P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

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

const int N = 1030;
int g[N][N];
int d[N];
stack<int> s;
int n;

void dfs(int u)
{
    for (int i = 1; i <= n; i++)
        if (g[u][i])
        {
            g[u][i]--, g[i][u]--;

            dfs(i);
        }

    s.push(u);
}

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

    int m;
    cin >> m;

    int a, b;
    int start = 1e9;
    while (m--)
    {
        cin >> a >> b;

        g[a][b]++, g[b][a]++;
        d[a]++, d[b]++;

        n = max({n, a, b});
        start = min({start, a, b});
    }

    for (int i = 1; i <= n; i++)
        if (d[i] & 1)
        {
            start = i;
            break;
        }

    dfs(start);

    while (s.size())
    {
        cout << s.top() << '\n';
        s.pop();
    }


    return 0;
}

P1341 无序字母对

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

const int N = 300;
bool g[N][N];
int d[N];
stack<char> stk;
int n;

void dfs(int u)
{
    for (int i = 0; i < N; i++)
        if (g[u][i])
        {
            g[u][i] = g[i][u] = false;

            dfs(i);
        }

    stk.push((char)u);
}

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

    cin >> n;

    string s;
    for (int i = 0; i < n; i++)
    {
        cin >> s;

        g[(int)s[0]][(int)s[1]] = g[(int)s[1]][(int)s[0]] = true;
        d[(int)s[0]]++;
        d[(int)s[1]]++;
    }

    int start = 0;
    int k = 0;
    for (int i = 0; i < N; i++)
        if (d[i] & 1)
        {
            k++;

            if (!start) start = i;
        }

    if (!start)
        for (int i = 0; i < N; i++)
            if (d[i])
            {
                start = i;
                break;
            }

    if (k && k != 2)
    {
        cout << "No Solution";
        return 0;
    }

    dfs(start);

    while (stk.size())
    {
        cout << stk.top();
        stk.pop();
    }


    return 0;
}

有向图的欧拉路径

定义: 在有向图中, 从点a到点b可以不重复经过所有的边, 那么称a到b为一条欧拉路径

有向图存在欧拉路径的充要条件:

1. 出度比入度大1的点的个数为1且入度比出度大1的点的个数为1

2. 或者所有点的出度等于入度

P7771 【模板】欧拉路径

1. n对字母全部出现在构造的字符串中, 且长度为n+1, 说明相邻2对字母对一定有1个字母相同;

2. 把字母当作点, 有公共字母的字母对就建边;

3. 跑欧拉路径即可;

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

const int N = 2e5 + 10;
int a[N], b[N];
int start[N], End[N], g[N];
int d1[N], d2[N];
stack<int> s;

void dfs(int u)
{
    for (int i = start[u]; i <= End[u]; i = start[u])
    {
        start[u]++;

        dfs(g[i]);
    }

    s.push(u);
}

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

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

    for (int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];

        d1[a[i]]++, d2[b[i]]++;
    }

    int res1 = 0, res2 = 0, root = 1;
    for (int i = 1; i <= n; i++)    
    {
        if (d1[i] - d2[i] > 1 || d1[i] - d2[i] > 1)
        {
            cout << "No";
            return 0;
        }

        if (d1[i] - d2[i] == 1) res1++, root = i;
        else if (d2[i] - d1[i] == 1) res2++;
    }

    if (!res1 && !res2 || res1 == 1 && res2 == 1)
    {
        int pre = 0;
        for (int i = 1; i <= n; i++)
        {
            d2[i] = start[i] = pre + 1;
            End[i] = pre + d1[i];
            pre = End[i];
        }

        for (int i = 1; i <= m; i++) g[d2[a[i]]++] = b[i];

        for (int i = 1; i <= n; i++) 
            sort(g + start[i], g + End[i] + 1);

        dfs(root);

        while (s.size())
        {
            cout << s.top() << ' ';
            s.pop();
        }
    }
    else cout << "No";

    return 0;
}

P6066 [USACO05JAN] Watchcow S

将一条无向边转化为2条有向边, 跑有向欧拉路径模板即可

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

const int N = 1e4 + 10, M = 1e5 + 10;
int h[N], e[M], ne[M], idx;
bool st[M];
stack<int> s;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];

        if (!st[i])
        {
            st[i] = true;

            dfs(j);
        }
    }

    s.push(u);
}

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

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

    memset(h, -1, sizeof h);

    int a, b;
    while (m--)
    {
        cin >> a >> b;

        add(a, b);
        add(b, a);
    }

    dfs(1);

    while (s.size())
    {
        cout << s.top() << '\n';
        s.pop();
    }


    return 0;
}