1
class Solution:
2
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
3
        # create the map
4
        adj = collections.defaultdict(list)
5
        for a, b in adjacentPairs:
6
            adj[a].append(b)
7
            adj[b].append(a)
8

9
        # find the start num
10
        start = adjacentPairs[0][0]
11
        for k, v in adj.items():
12
            if len(v) == 1:
13
                start = k
14
                break
15

16
        # dfs to connect the graph
17
        nums = []
18
        seen = set()
19

20
        def dfs(num):
21
            seen.add(num)
22
            for next_num in adj[num]:
23
                if next_num in seen:
24
                    continue
25
                dfs(next_num)
26
            nums.append(num)
27

28
        dfs(start)
29
        return nums