ปัญหา
ให้อาร์เรย์ nums (ค่า 0 ถึง n-1 ไม่ซ้ำ) และรายการคู่ดัชนี pairs ที่อนุญาตให้สลับได้ ตรวจสอบว่าสามารถเรียงอาร์เรย์ได้หรือไม่
ตัวอย่าง
nums = [6,1,7,3,0,5,4,2], pairs = [(0,4),(6,0),(2,7)] → สลับได้เป็น [0,1,2,3,4,5,6,7] → True
แนวคิดการแก้ปัญหา (Graph + BFS)
- สร้างกราฟจาก pairs (ดัชนีเป็นโหนด)
- หา Connected Components ด้วย BFS/DFS
- ในแต่ละ Component: ดัชนีที่อยู่ใน component เดียวกัน สลับกันได้อย่างอิสระ
- ดังนั้น ค่าที่อยู่ใน component ต้องตรงกับดัชนีที่อยู่ใน component นั้น (หลังเรียง)
โค้ดตัวอย่าง
from collections import deque
def solve(nums, pairs):
n = len(nums)
graph = [[] for _ in range(n)]
for u, v in pairs:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
for i in range(n):
if not visited[i]:
queue = deque([i])
visited[i] = True
indices = []
values = []
while queue:
u = queue.popleft()
indices.append(u)
values.append(nums[u])
for v in graph[u]:
if not visited[v]:
visited[v] = True
queue.append(v)
if sorted(indices) != sorted(values):
return False
return True
print(solve([6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)])) # True
อินพุต / เอาต์พุต
Input: [6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)] Output: True
