题目地址：

https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/description/

给定一个长$n$的数组$a$， a [ i ] = { x , y } a[i]=\{x,y\} a[i]={x,y}表示某个数组$b$里$x,y$相邻。题目保证$b$的所有数字各不相同，并且$b$的相邻位置的数的数对一定出现在$a$中（顺序不保证），要求返回$b$。答案不唯一的话返回任意一个。题目保证答案存在，且$\forall i,-10^5\le b[i]\le 10^5$。

将$a$视为图的所有边，我们找到度为$1$的点，这个点一定在$b$的两端，直接放在最左端，然后找这个数的邻居，一个个填上去。在填$x$的时候，需要维护上次填的数是谁，这样枚举$x$的邻居的时候需要略过上次填的数。代码如下：

class Solution {
public:
  vector<int> restoreArray(vector<vector<int>> &ps) {
    unordered_map<int, vector<int>> g;
    for (auto &p : ps) {
      int x = p[0], y = p[1];
      g[x].push_back(y);
      g[y].push_back(x);
    }

    int st = -2e9;
    for (auto &[k, v] : g)
      if (v.size() == 1) {
        st = k;
        break;
      }

    int n = ps.size() + 1;
    vector<int> res;
    res.reserve(n);

    int prev = -2e9, cur = st;
    while (res.size() < n) {
      res.push_back(cur);
      auto it = g.find(cur);
      assert(it != g.end());
      for (int ne : it->second)
        if (ne != prev) {
          prev = cur;
          cur = ne;
          break;
        }
    }
    return res;
  }
};

时空复杂度$O(n)$。