# Eulerian Circuit / Path 歐拉迴路/路徑

[video link](https://www.bilibili.com/video/BV1Y341177eW/?spm_id_from=333.337.search-card.all.click&vd_source=4744729f0e634c83cabafd5211f4983b)

>[!Note]
>用來判斷一筆的(一筆走過圖形的所有邊，不可重複)
>如果`indegree`為基數，則無法成為歐拉迴圈

>[!Tip]
>迴圈: start == end
>路徑: start != end

用`degree`來判斷起始點(如果為迴圈則可以選任意一點)

- 連接圖形

vector<int> path; // 答案
stack<int> st;
st.push(start);

while(!st.empty()){
    vector<int> &next = adj[st.top()] // adj 為可以到的點之集合
        // 沒點可以走 ==> 最後一點
        if(next.empty()){
            path.push_back(st.top());
            st.pop();
        }
        else{
            //將點加入
            st.push(next.back());
            // 刪除走過的點
            next.pop_back();
        }
}

reverse(path.begin(), path.begin() + path.size() - 1 );

## 題目

:::spoiler 📖[LeetCode] 2097. Valid Arrangement of Pairs

[question link](https://leetcode.com/problems/valid-arrangement-of-pairs/description/?envType=daily-question&envId=2024-11-30)

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        map<int, vector<int>> adj;
        map<int, int> degree;

        // 計算 degree && 連接圖 
        for(auto it : pairs){
            adj[it[0]].push_back(it[1]);
            degree[it[0]]++;
            degree[it[1]]--;
        }

        // 根據題意，可以判斷基數為起點，如果是歐拉迴圈，用第一個點
        int start = pairs[0][0];
        for(auto [node, deg] : degree){
            if(deg == 1){
                start = node;
                break;
            }
        }

        // 連接圖
        stack<int> st;
        vector<int> path;
        st.push(start);

        while(!st.empty()){
            vector<int> &nebor = adj[st.top()];

            if(nebor.empty()){
                path.push_back(st.top());
                st.pop();
            }
            else{
                st.push(nebor.back());
                nebor.pop_back();
            }
        }

        vector<vector<int>> ans;

        for(int i = path.size() - 1; i > 0; i--){
            ans.push_back({ path[i], path[i-1] });
        }

        return ans;

    }
};

:::

:::spoiler 📖[LeetCode] 332. Reconstruct Itinerary

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        map<string, vector<string>> adj;

        for (auto& ticket : tickets) {
            adj[ticket[0]].push_back(ticket[1]);
        }
        for (auto& [key, neighbors] : adj) {
            sort(neighbors.rbegin(), neighbors.rend()); // 使用反向排序，方便 pop_back()
        }

        vector<string> path;
        stack<string> st;
        st.push("JFK"); 

        // Hierholzer's Algorithm
        while (!st.empty()) {
            string curr = st.top();
            if (adj[curr].empty()) {
                path.push_back(curr);
                st.pop();
            } else {
                st.push(adj[curr].back());
                adj[curr].pop_back();
            }
        }

        reverse(path.begin(), path.end());
        return path;
    }
};

:::