โปรแกรมกู้คืนอาร์เรย์จากคู่ที่อยู่ติดกันใน Python

ได้รับอาร์เรย์ 2D adPair ขนาด n-1 ที่ adPair[i]=[ui,vi] หมายถึง ui,vi ติดกันในอาร์เรย์ nums (มี n ค่า unique) ต้องคืนอาร์เรย์ nums เดิม

ตัวอย่าง: adPair=[[3,2],[4,5],[4,3]] ผลลัพธ์ [2,3,4,5]

วิธีแก้ปัญหา

1. สร้าง my_map adjacency list จาก adPair
2. หาจุดเริ่มต้น: โหนดที่มี neighbor เพียง 1 ตัว
3. สร้าง nums = [start, neighbor]
4. วนต่อยอด: ดู neighbor ของตัวสุดท้าย เลือกตัวที่ไม่ใช่ตัวก่อนหน้า

ตัวอย่างโค้ด

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))

อินพุต

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

เอาต์พุต

[2, 3, 4, 5]