पायथन में जांचें कि दी गई इंडेक्स पर स्वैप करके सरणी को क्रमबद्ध किया जा सकता है या नहीं

मान लीजिए हमारे पास एक सरणी nums है जिसमें [0, n-1] रेंज के अद्वितीय मान हैं। यह सरणी असॉर्टेड है। हमारे पास इंडेक्स के युग्मों की एक और सरणी है जहां सरणी के तत्वों को स्वैप किया जा सकता है। हम कई बार स्वैप कर सकते हैं। हमें जांचना है कि क्या हम इन स्वैप का उपयोग करके सरणी को क्रमबद्ध क्रम में व्यवस्थित कर सकते हैं।

उदाहरण के लिए, nums = [6, 1, 7, 3, 0, 5, 4, 2], pairs = [(0,4), (6,0), (2,7)] के लिए आउटपुट True होगा।

हल करने का तरीका

1. ग्राफ बनाएं जहां इंडेक्स नोड्स हैं और pairs एज हैं
2. प्रत्येक कनेक्टेड कंपोनेंट के लिए:
   • कंपोनेंट के इंडेक्स और मान इकट्ठा करें
   • दोनों को सॉर्ट करें
   • यदि सॉर्ट किए गए इंडेक्स और मान मेल नहीं खाते, तो False लौटाएं
3. True लौटाएं

उदाहरण कोड

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

इनपुट

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

आउटपुट

True