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

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

तो अगर इनपुट n =3, red_edges =[[0,1],[1,2]] और blue_edges =[] जैसा है, तो आउटपुट [0, 1, -1]

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

• bfs() नामक एक विधि को परिभाषित करें, इसमें re, be, f और n की आवश्यकता होगी

• विज़िट किए गए सेट को परिभाषित करें, एक कतार को परिभाषित करें और एक ट्रिपल डालें [0, f, 0]

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

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

  • रंग:=रंग के मूल्य का पूरक (सत्य से असत्य और इसके विपरीत)

  • रेस [वर्तमान] :=मिनट का रेस [वर्तमान] और चरण

  • अगर रंग शून्य नहीं है, तो

    • प्रत्येक के लिए मैं फिर से [वर्तमान]

      • यदि जोड़ी (i, रंग) का दौरा नहीं किया गया है, तो विज़िट में (i, रंग) डालें और [i, रंग, चरण + 1] को q

        में डालें

  • अन्यथा जब रंग 0 हो, तब

    • प्रत्येक मैं के लिए [वर्तमान]

      • यदि जोड़ी (i, रंग) का दौरा नहीं किया गया है, तो विज़िट में (i, रंग) डालें और [i, रंग, चरण + 1] को q

        में डालें

• मुख्य विधि में -

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

• फिर से और हो:=n खाली सरणियों के सरणियाँ

• प्रत्येक तत्व के लिए मैं r में:i[1] को पुनः [i[0]]

  . में सम्मिलित करता हूं

• b में प्रत्येक तत्व के लिए:i[1] को be[i[0]]

  . में डालें

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

• मैं के लिए 0 से लेकर रेस की लंबाई तक -1

  • अगर res[i] =inf, तो res[i] :=-1

• रिटर्न रेस

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

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

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]