# 歐拉迴路

[TOC]

一條洽走過所有邊一次的路徑稱為歐拉路徑，若起點與終點相同則稱為歐拉迴路。
# 觀察
若一張無向圖存在歐拉迴路，則圖為連通的且每個點的度數皆為偶數，必要性顯然，每個點出去的次數都等於進入的次數。故我們在此證明必要性:

選定一個起點，我們一定可以找到一條回到起點的路徑(Trivial)，若把這些邊拔掉，圖上每個點的度數依然為偶數，則對於此路徑上的任一個節點我們都可以在找到一條回到該節點的路徑，如此重複並把所有路徑相加便會得到歐拉迴路。

歐拉路徑只是把歐拉迴路再拔掉一條邊。
# 實作
先隨便走直到走回起點(即走到沒有路)，把最後一條邊加入答案，往前看上一個節點，再一直走直到回到自己。
會發現，這不就是DFS的後序嗎，因此code如下:

void dfs(int pos){
    while(!g[pos].empty()){
        int i=g[pos].front();
        g[pos].erase(i);
        g[i].erase(pos);
        dfs(i);
    }
    ans.push_back(pos);
}

注意這是紀錄路徑上的點的寫法，若要紀錄邊要再修改。
# 有向圖
有向圖存在非迴路的歐拉路徑的充要條件:
* 連通圖
* 起點的出邊比入邊多一條
* 終點的入邊比出邊多一條
* 其餘的點兩種邊一樣多
找解的方式與無向圖相同
# K筆畫
對於每個連通塊，新增一個節點，並把所有奇點都連到這個點。照著原方法做，最後再把這個節點刪掉。

# 題目
## [Mail Delivery](https://cses.fi/problemset/task/1691/)
無向圖裸題

---
## [Fair Share](https://codeforces.com/problemset/problem/1634/E)
:::spoiler 解法:
對每一個陣列和每一種數字各建一個點，將陣列節點與陣列內的數字個連一條邊，條件轉換如下:
* 每個陣列有一半L一半R$\Longrightarrow$每個陣列節點的入邊和出邊數量一樣
* 每個數字有一半L一半R$\Longrightarrow$每個數字節點的入邊和出邊數量一樣

找歐拉迴路就好
:::

---
## [Teleporters Path](https://cses.fi/problemset/task/1693/)
有向圖裸題

---
## [P1341 无序字母对](https://www.luogu.com.cn/problem/P1341)

[洛谷 P1127 词链](https://www.luogu.com.cn/problem/P1127)和[洛谷 P1333 瑞瑞的木棍](https://www.luogu.com.cn/problem/P1333)也是類似的題目

:::spoiler code:

#include<bits/stdc++.h>
using namespace std;
vector<char> ans;
vector<set<int>> g(52);
vector<int> doo(52);
void dfs(int pos){
    while(!g[pos].empty()){
        int i=*g[pos].begin();
        g[pos].erase(i);
        g[i].erase(pos);
        dfs(i);
    }
    ans.push_back(pos>=26? 'a'+(pos-26):'A'+pos);
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string s;
        int a,b;
        cin>>s;
        if(s[0]<='Z') a=s[0]-'A';
        else{
            a=s[0]-'a';
            a+=26;
        }
        if(s[1]<='Z'){
            b=s[1]-'A';
        }
        else{
            b=s[1]-'a';
            b+=26;
        }
        g[a].insert(b);
        g[b].insert(a);
        doo[a]++;
        doo[b]++;
    }
    int cnt=0;
    for(int i:doo) if(i%2==1) cnt++;
    if(cnt>2){
        cout<<"No Solution"<<endl;
        return 0;
    }
    for(int i=0;i<52;i++){
        if(!g[i].empty()&&(cnt==0||doo[i]%2==1)){
            dfs(i);
            break;
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto i:ans)cout<<i;
    cout<<endl;
    return 0;
}

:::

---
## [D. Tanya and Password](https://codeforces.com/problemset/problem/508/D)
:::spoiler 提示:
就只是上面那一題的延伸而已，因此思考怎麼變成上面那一題的形式
:::
[題解](https://codeforces.com/blog/entry/16048?locale=en)

---
## [Senior Postmen](https://oj.uz/problem/view/BOI14_postmen)
[題解](https://github.com/boi-2014/tasks/blob/master/solutions/analysis/postmen.tex)

---

# reference
2023 IOI Camp