p.s. 二者的必要條件是圖為連通圖

歐拉圖

定義

歐拉通路：能一次性走完一張圖上所有的邊，且每條邊只經過一次
歐拉回路：能一次性走完一張圖上所有的邊，每條邊只經過一次，且這條路徑構成一個回路（即最終回到了出發點）

有歐拉回路的圖成為歐拉圖（Eulerian），有歐拉通路但無回路的稱為半歐拉圖（semi-Eulerian）

歐拉回路必須滿足的條件：

無向圖：度數為奇數的點的個數 == 0 或者 == 2（== 0 ： 歐拉回路， == 2 ：歐拉通路）

有向圖：除了起點和終點，每個點的入度 == 出度，滿足 起點的出度-入度 == 1 && 終點入度-出度 == 1 或者 起點終點為同一個

思路

dfs。

首先需要確定dfs的起點，這可以通過輸入邊時統計度數實現，如果奇數度數的點不是0或2，則無歐拉通路；有兩個奇數點的，找到其中一個點作為起點；度數全為偶數的，任意指定一個點作為起點。

然后開始dfs，每經過一條路時就把它的次數--，免得重復經過，當無路可走時，就存下當前的點（注意是逆序），回溯，繼續遍歷

模版題1

https://www.luogu.com.cn/problem/P2731

這題不僅要先判斷，還要輸出字典序最小的遍歷序列，這里有坑。

關于為什么不能正序輸出但可以倒序：

首先，在無向圖中，如果有一條歐拉路，起點為 \(v\) ，用一個點 \(u\) 向已知起點 \(v\) 再連一條邊，那么現在就有了從 \(u\) 出發的一條歐拉路。

倒序輸出相當于，之前先找到了以 \(v\) 為起點的一條歐拉路，即先解決子問題，現在在它前面加入\(u\)

正序輸出相當于，給你一個大問題，你沒有解決子問題，但是先規定先從當前點出發，不能保證從當前出發能找到歐拉路的正確性

code

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 500 + 10;
int m, n = 500, u, v;
int rd[N], path[N][N];
int start = 1;
int cnt, ans[N];

void dfs(int u) {
    for(int i = 1; i <= 500; i++) {
        if(path[u][i]) {
            path[u][i]--;
            path[i][u]--;  //  有向圖刪掉
            dfs(i);
        }
    }
    ans[++cnt] = u;
}

int main() {  
    ios::sync_with_stdio(false);
    cin >> m;
    for(int i = 1; i <= m; i++) {
        cin >> u >> v;
        path[u][v]++; path[v][u]++;
        rd[u]++; rd[v]++;
    }
    for(int i = 1; i <= 500; i++) {
        if(rd[i] % 2) {
            start = i;
            break;
        }
    }
    dfs(start);
    for(int i = cnt; i >= 1; i--) cout << ans[i] << endl;
    return 0;
}

模版題2

https://www.luogu.com.cn/problem/P1341

感覺建圖挺有意思的，可以自己先思考。

一對點對相當于給這兩個字母連了一條無向邊。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 500 + 10;
int m, n = 500;
string s;
int rd[N], path[N][N];
int start;
int cnt, ans[N];

inline int chg(char ch) {
    return (int)(ch);
}

void dfs(int u) {
    for(int i = 1; i <= 200; i++) {
        if(i >= 'a' && i <= 'z' || i >= 'A' && i <= 'Z') {
            if(path[u][i]) {
                path[u][i]--;
                path[i][u]--;  //  有向圖刪掉
                dfs(i);
            }
        }
    }
    ans[++cnt] = u;
}

int main() {  
    ios::sync_with_stdio(false);
    cin >> m;
    for(int i = 1, u, v; i <= m; i++) {
        cin >> s;
        u = chg(s[0]); v = chg(s[1]);
        path[u][v]++; path[v][u]++;
        rd[u]++; rd[v]++;
    }
    int odd = 0;
    for(int i = 1; i <= 200; i++) {
        if(i >= 'a' && i <= 'z' || i >= 'A' && i <= 'Z') {
            if(rd[i] % 2) {
                odd++;
            }
        }
    }
    if(odd != 0 && odd != 2) {
        cout << "No Solution\n";
        return 0;
    }
    if(odd == 0) {
        for(int i = 1; i <= 200; i++) {
            if(rd[i]) {
                start = i;
                break;
            }
        }
    }
    else {
        for(int i = 1; i <= 200; i++) {
            if(rd[i] % 2) {
                start = i;
                break;
            }
        }
    }
    dfs(start);
    // cout << "cnt = " << cnt << endl; /// 
    for(int i = cnt; i >= 1; i--) cout << (char)ans[i];
    cout << '\n';
    return 0;
}

哈密爾頓圖

定義

哈密爾頓路：經過一張圖上所有的點的通路
哈密爾頓回路：經過一張圖上所有的點的通回路

有哈密爾頓回路的圖成為哈密爾頓圖（Hamilton），有哈密爾頓通路但無回路的稱為半哈密爾頓圖（semi-Hamilton）