learning/l33tcode/restore-the-array-from-adjacent-pairs.py at master · fspv/learning · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from collections import defaultdict
from typing import Counter, DefaultDict, List, Set


class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        # Build graph
        graph: DefaultDict[int, Set[int]] = defaultdict(set)
        indegrees: Counter[int] = Counter()
        for src, dst in adjacentPairs:
            graph[src].add(dst)
            graph[dst].add(src)
            indegrees[src] += 1
            indegrees[dst] += 1

        # Find one of the two edge nodes
        edge_node = 0
        for node, indegree in indegrees.items():
            if indegree == 1:
                edge_node = node
                break

        # Traverse from the edge
        prev_node = edge_node
        node = graph[prev_node].pop()

        result: List[int] = [edge_node]

        while indegrees[node] != 1:
            result.append(node)
            graph[node].discard(prev_node)
            prev_node = node
            node = graph[prev_node].pop()

        # Append the second edge node
        result.append(node)

        return result