Restore the Array From Adjacent Pairs（C++从相邻元素对还原数组）

比眉伴天荒 2022-11-07 13:21 246阅读 0赞

解题思路：

(1)dfs

class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
        unordered_map<int,int> mp;
        unordered_map<int,vector<int>>mt;
        for(int i=0;i<adjacentPairs.size();i++) {
            mp[adjacentPairs[i][0]]++;
            mp[adjacentPairs[i][1]]++;
            mt[adjacentPairs[i][0]].push_back(adjacentPairs[i][1]);
            mt[adjacentPairs[i][1]].push_back(adjacentPairs[i][0]);
        }
        int start=0;
        for(auto it=mp.begin();it!=mp.end();it++) {
            if(it->second==1) start=it->first;
            it->second=0;
        }
        vector<int> v(1,start);
        mp[start]=1;
        while((mt[start].size()==1 && mp[mt[start][0]]==0) || (mp[mt[start][0]]==0 || mp[mt[start][0]]==1)) {
            if(mp[mt[start][0]]==0) {
                v.push_back(mt[start][0]);
                mp[mt[start][0]]=1;
                start=mt[start][0];
            } else if(mt[start].size()==1) return v;
            else {
                v.push_back(mt[start][1]);
                mp[mt[start][1]]=1;
                start=mt[start][1];
            }
        }
        return v;
    }
};