Chương trình khôi phục mảng từ các cặp liền kề trong Python

Mô tả bài toán

Cho mảng 2D adPair kích thước n-1, mỗi adPair[i] = [ui, vi] cho biết ui và vi liền kề trong mảng nums (có n phần tử duy nhất). Khôi phục mảng nums.

Ví dụ

adPair = [[3,2],[4,5],[4,3]] -> [2,3,4,5].

Giải thuật

1. Xây dựng đồ thị kề my_map từ các cặp.
2. Tìm phần tử có bậc 1 (đầu mảng), khởi tạo nums = [a, l[0]].
3. Mở rộng mảng: lấy hai hàng xóm của phần tử cuối, chọn cái không phải phần tử trước đó.

Triển khai Python

from collections import defaultdict

def solve(adPair):
    my_map = defaultdict(list)
    for a, b in adPair:
        my_map[a].append(b)
        my_map[b].append(a)
    for a, l in my_map.items():
        if len(l) == 1:
            nums = [a, l[0]]
            break
    for i in range(1, len(adPair)):
        a, b = my_map[nums[-1]]
        if a == nums[-2]:
            nums.append(b)
        else:
            nums.append(a)
    return nums

adPair = [[3,2],[4,5],[4,3]]
print(solve(adPair))

Đầu vào

[[3,2],[4,5],[4,3]]

Đầu ra

[2, 3, 4, 5]