1743. Restore the Array From Adjacent Pairs

一樣被打爆,

這題最難的問題在於, 你要怎麼找到頭尾分別是誰

這邊有個很好的dfs解法, 主要就是我們不管從頭, 或從尾開始, 題目都接受,

所以我們首先先記錄每個數字後面對應到的vector, 然後我們挑其中一個頭尾開始去做一個dfs的過程, 並在過程中記錄下來

紀錄完之後, 走過就加到答案裡

class Solution {
public:
    void dfs(unordered_map<int, vector<int>> &m, unordered_set<int> &visited, int node, vector<int> &res){
        if(visited.count(node) != 0){
            return;
        }
        res.push_back(node);
        visited.insert(node);
        for(auto n: m[node]){
            dfs(m, visited, n, res);
        }
    }
    vector<int> restoreArray(vector<vector<int>>& A) {
        unordered_map<int, vector<int>> m;
        for(auto &a: A){
            m[a[0]].push_back(a[1]);
            m[a[1]].push_back(a[0]);
        }
        int head;
        for(auto a: m){
            if(a.second.size() == 1){
                head = a.first;
                break;
            }
        }
        unordered_set<int> visited;
        vector<int> res;
        dfs(m, visited, head, res);
        return res;
}
};