পাইথনে নির্দিষ্ট ইন্ডেক্সের মধ্যে সোয়্যাপ করে অ্যারে সোর্ট করা সম্ভব কিনা

একটি অ্যারে nums (unique, 0 থেকে n-1) এবং সোয়্যাপযোগ্য ইন্ডেক্স পেয়ারগুলো দেওয়া আছে। এই সোয়্যাপগুলো ব্যবহার করে অ্যারেটি সর্ট করা সম্ভব কিনা যাচাই করতে হবে।

উদাহরণ

ইনপুট: nums = [6,1,7,3,0,5,4,2], pairs = [(0,4),(6,0),(2,7)]

আউটপুট: True

অ্যালগরিদম (BFS কনেক্টেড কম্পোনেন্ট)

1. পেয়ারগুলো থেকে অ্যাাডজেসেন্সি লিস্ট বানান।
2. প্রতিটি কনেক্টেড কম্পোনেন্টের ইন্ডেক্স এবং 거기에 থাকা ভ্যালু দুটি আলাদা লিস্টে নিন।
3. দুটি লিস্ট সর্ট করে তুলনা করুন। সমান হলে সোয়্যাপ দিয়ে সর্ট করা সম্ভব।

উদাহরণ কোড

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))  # Output: True

ইনপুট

[6,1,7,3,0,5,4,2], [(0,4),(6,0),(2,7)]

আউটপুট

True