पायथन में वैकल्पिक रंगों के साथ सबसे छोटा पथ

मान लीजिए हमारे पास एक डायरेक्टेड ग्राफ है, जिसमें नोड्स 0, 1, ..., n-1 लेबल किए गए हैं। इस ग्राफ में, प्रत्येक एज या तो लाल या नीले रंग से रंगी हुई है, और सेल्फ-एज या समानांतर एज हो सकते हैं। red_edges में प्रत्येक [i, j] नोड i से नोड j तक एक लाल डायरेक्टेड एज दर्शाता है। इसी तरह, blue_edges में प्रत्येक [i, j] नोड i से नोड j तक एक नीली डायरेक्टेड एज दर्शाता है। हमें लंबाई n का एक ऐरे answer ढूंढना है, जहां प्रत्येक answer[X] नोड 0 से नोड X तक के सबसे छोटे पथ की लंबाई है जैसे कि पथ के साथ एज रंग वैकल्पिक हों (या -1 यदि ऐसा पथ मौजूद नहीं है)।

इसलिए यदि इनपुट n = 3, red_edges = [[0,1],[1,2]] और blue_edges = [] है, तो आउटपुट [0, 1, -1] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• bfs() नामक एक मेथड परिभाषित करें, यह re, be, f और n लेगा

• visited नामक एक सेट परिभाषित करें, एक क्यू परिभाषित करें और ट्रिपलेट [0, f, 0] इन्सर्ट करें

• जब तक q खाली नहीं है

  • करंट, कलर, स्टेप को q[0] के रूप में सेट करें, और q से हटाएं

  • कलर := कलर के मान को पूरक करें (true से false और इसके विपरीत)

  • res[current] := res[current] और स्टेप का न्यूनतम

  • यदि कलर नॉन-जीरो है, तो

    • re[current] में प्रत्येक i के लिए

      • यदि जोड़ी (i, कलर) visited में नहीं है, तो (i, कलर) को visited में इन्सर्ट करें और [i, कलर, स्टेप + 1] को q में इन्सर्ट करें

  • अन्यथा जब कलर 0 है, तो

    • be[current] में प्रत्येक i के लिए

      • यदि जोड़ी (i, कलर) visited में नहीं है, तो (i, कलर) को visited में इन्सर्ट करें और [i, कलर, स्टेप + 1] को q में इन्सर्ट करें

• मुख्य मेथड में -

• res := अनंत मानों का एक ऐरे और इसका आकार n है

• re और be := n खाली ऐरे के ऐरे

• r में प्रत्येक एलिमेंट i के लिए: re[i[0]] में i[1] इन्सर्ट करें

• b में प्रत्येक एलिमेंट i के लिए: be[i[0]] में i[1] इन्सर्ट करें

• bfs(re, be, false, n) और bfs(re, be, true, n) कॉल करें

• i को 0 से res की लंबाई - 1 तक रेंज में

  • यदि res[i] = inf, तो res[i] := -1

• res लौटाएं

उदाहरण (पायथन)

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

class Solution(object):
    def shortestAlternatingPaths(self, n, r, b):
        self.res = [float(\"inf\")] * n
        re = [[] for i in range(n) ]
        be = [[] for i in range(n) ]
        for i in r:
            re[i[0]].append(i[1])
        for i in b:
            be[i[0]].append(i[1])
        self.bfs(re,be,False,n)
        self.bfs(re,be,True,n)
        for i in range(len(self.res)):
            if self.res[i] == float('inf'):
                self.res[i]=-1
        return self.res
    def bfs(self,re,be,f,n):
        visited = set()
        queue = [[0,f,0]]
        while queue:
            current,color,step = queue[0]
            queue.pop(0)
            color = not color
            self.res[current] = min(self.res[current],step)
            if color:
                for i in re[current]:
                    if (i,color) not in visited:
                        visited.add((i,color))
                        queue.append([i,color,step+1])
            elif not color:
                for i in be[current]:
                    if (i,color) not in visited:
                        visited.add((i,color))
                        queue.append([i,color,step+1])

ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1], [1,2]], []))

इनपुट

3 [[0,1],[1,2]] []

आउटपुट

[0,1,-1]