Cho mảng nums chứa các giá trị duy nhất từ 0 đến n-1 (chưa sắp xếp). Cũng cho một mảng các cặp chỉ số pairs cho phép hoán vị các phần tử tại các chỉ số đó. Có thể hoán vị nhiều lần. Kiểm tra xem có thể sắp xếp mảng theo thứ tự tăng dần chỉ bằng các hoán vị cho phép hay không.
Ví dụ: nums = [6,1,7,3,0,5,4,2], pairs = [(0,4),(6,0),(2,7)] → True.
Giải thuật
- Xây dựng đồ thị các chỉ số có thể hoán vị (danh sách kề).
- Duyệt các thành phần liên thông (BFS/DFS). Với mỗi thành phần, lấy tập chỉ số và tập giá trị tại các chỉ số đó.
- Sắp xếp cả hai tập, nếu chúng không giống nhau → không thể sắp xếp →
False. - Nếu tất cả thành phần thỏa mãn →
True.
Mã ví dụ
from collections import deque
def solve(nums, pairs):
N = len(nums)
P = len(pairs)
v = [[] for _ in range(N)]
visited = set()
for i in range(P):
v[pairs[i][0]].append(pairs[i][1])
v[pairs[i][1]].append(pairs[i][0])
for i in range(N):
if i not in visited:
que = deque()
arr_first = []
arr_second = []
visited.add(i)
que.append(i)
while que:
u = que.popleft()
arr_first.append(u)
arr_second.append(nums[u])
for s in v[u]:
if s not in visited:
visited.add(s)
que.append(s)
arr_first.sort()
arr_second.sort()
if arr_first != arr_second:
return False
return True
nums = [6,1,7,3,0,5,4,2]
pairs = [(0,4),(6,0),(2,7)]
print(solve(nums, pairs))
Đầu vào
[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]
Đầu ra
True