1743. Restore the Array From Adjacent Pairs

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. The pairs can appear in any order.

Return the original array nums. If there are multiple solutions, return any of them.

class Solution {
    void dfs(unordered_map<int, vector<int>>& adj, int u, vector<int>& res, int par = INT_MIN) {
        res.push_back(u);
        for(auto& v : adj[u]) {
            if(v == par) continue;
            dfs(adj, v, res, u);
        }
    }
public:
    vector<int> restoreArray(vector<vector<int>>& A) {
        unordered_map<int, vector<int>> adj;
        for(auto& a : A) {
            int u = a[0], v = a[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        vector<int> res;
        
        for(auto& [u, vs] : adj) {
            if(vs.size() == 1) {
                dfs(adj, u, res);
                return res;
            }
        }
        
        return res;
    }
};