Leetcode 1866 Solution

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)

        for node1, node2 in adjacentPairs:
            graph[node1].append(node2)
            graph[node2].append(node1)

        head = None
        for src, dsts in graph.items():
            if len(dsts) == 1:
                head = src
                break

        assert head is not None

        ans = [head]
        prev_node = None
        node = head
        while len(ans) < len(adjacentPairs) + 1:
            for neighbor in graph[node]:
                if neighbor == prev_node:
                    continue

                ans.append(neighbor)
                prev_node = node
                node = neighbor
                break
            else:
                raise Exception()

        return ans