Luogu P1341 – 欧拉路径

PROBLEM

https://www.luogu.org/problemnew/show/P1341

ANALYSIS

找到无向图中字典序最小的欧拉路径（不一定是回路），不存在则输出No Solution .

起初考虑复杂了，写了一个没脑子的暴搜。

一笔画问题，如果有奇数入度节点，若数量不为2，则构不成欧拉回路。

如果数量为2，则一定从某一奇数入度节点开始画。

如果没有奇数入度结点，那么任何节点都可以作为起始点。

字典序还是比较好处理的。

定理一

1. 连通的无向图G有欧拉路径的充要条件是：  G中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。
   （实际上，连通无向图中，奇顶点的数目总是偶数。）
2. 连通的无向图G是欧拉环（存在欧拉回路）的充要条件是：G中每个顶点的度都是偶数。

定理二

如果连通无向图G有2k个奇顶点，那么它可以用k笔画成，并且至少要用k笔画成。

SOLUTION

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 10010;
int n, m, d[N][N], ans, c[52];
char ind[N], s[N];

void dfs(int x) {
    for (int e : c)
        if (d[x][e] > 0) {
            d[x][e]--;
            d[e][x]--;
            dfs(e);
        }
    s[++ans] = x;
}

int main() {
    for (int i = 0, j = 'A'; i != 26; i++, j++) {
        c[i] = j;
    }
    for (int i = 26, j = 'a'; i != 52; i++, j++) {
        c[i] = j;
    }
    cin >> m;
    char u, v;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        d[u][v]++;
        d[v][u]++;
        ind[v]++;
        ind[u]++;
    }
    int cnt = 0, h = 0;
    for (int i : c)
        if (ind[i] & 1) {
            cnt++;
            if (!h) {
                h = i;
            }
        }
    if (!h)
        for (int i : c)
            if (ind[i]) {
                h = i;
                break;
            }
    // 判断是否为欧拉回路(连通图)
    if (cnt && cnt != 2) {
        puts("No Solution");
        return 0;
    }
    dfs(h);
    if (ans < m + 1) {
        puts("No Solution");
        return 0;
    }
    for (int i = ans; i >= 1; i--) {
        printf("%c", s[i]);
    }
    putchar('\n');
    return 0;
}

REFERENCE

1. https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98
2. https://www.luogu.org/problemnew/solution/P1341

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.