यह जांचने का कार्यक्रम कि क्या हम सभी कमरों को अजगर में अनलॉक कर सकते हैं या नहीं

मान लीजिए हमारे पास सूचियों की एक सूची है जिसे कमरे कहा जाता है। कमरों में प्रत्येक सूचकांक एक कमरे का प्रतिनिधित्व करता है और कमरे [i] अन्य कमरों को खोलने के लिए विभिन्न चाबियों का प्रतिनिधित्व करता है। कमरा 0 खुला है और हम उस कमरे में हैं और हर दूसरे कमरे में ताला लगा हुआ है। हम खुले कमरों के बीच स्वतंत्र रूप से घूम सकते हैं; हमें यह देखना होगा कि हम हर कमरा खोल सकते हैं या नहीं।

इसलिए, यदि इनपुट कमरे की तरह है =[[2, 0], [3], [1, []], तो आउटपुट सही होगा, क्योंकि हम कमरे 0 से शुरू करते हैं और इसकी चाबी के साथ कमरे 2 में जा सकते हैं 2. कक्ष 2 से हम कक्ष 1 में जा सकते हैं। फिर कक्ष 3 की चाबी लेकर उसे खोलें। तो सब खुल गए।

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

• n :=कमरों का आकार
• तैयार:=एकल तत्व 0 के साथ एक सूची
• देखा:=एक नया सेट
• जबकि तैयार खाली नहीं है, करें
  • u :=तैयार का अंतिम तत्व और इसे तैयार से हटा दें
  • आपको देखा गया के रूप में चिह्नित करें
  • कमरे में प्रत्येक वी के लिए[यू], करते हैं
    • यदि v नहीं देखा जाता है, तो
      • तैयार होने के अंत में v डालें
• सही लौटें जब सीन का आकार n के समान हो, अन्यथा गलत।

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

उदाहरण

class Solution:
   def solve(self, rooms):
      n = len(rooms)

      ready = [0]
      seen = set()

      while ready:
         u = ready.pop()
         seen.add(u)

         for v in rooms[u]:
            if v not in seen:
               ready.append(v)

      return len(seen) == n

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

इनपुट

rooms = [[2, 0],[3],[1],[]]

आउटपुट

True