टारगेट को धारण करने वाले सबसे छोटे चक्र की लंबाई ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास एक निर्देशित ग्राफ की आसन्न सूची है, जहां इंडेक्स i पर प्रत्येक सूची नोड i से जुड़े नोड्स को दर्शाती है। हमारे पास एक टारगेट मान भी है। हमें उस सबसे छोटे चक्र की लंबाई ढूंढनी है जिसमें टारगेट शामिल है। यदि कोई समाधान नहीं है तो -1 लौटाएं।

उदाहरण के लिए, यदि इनपुट इस तरह है:

target = 3, तो आउटपुट 3 होगा, क्योंकि चक्र नोड्स 1 → 2 → 3 → 1 है। ध्यान दें कि एक और चक्र 0 → 1 → 2 → 3 → 0 है, लेकिन यह सबसे छोटा नहीं है।

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

visited := एक नया सेट
l := target तत्व के साथ एक सूची
length := 0
जब तक l खाली नहीं है, करें
- length := length + 1
- nl := एक नई सूची
- प्रत्येक u के लिए l में, करें
  - प्रत्येक v के लिए graph[u] में, करें
    - यदि v, target के समान है, तो
      - length लौटाएं
    - यदि v विज़िटेड है, तो
      - अगली पुनरावृत्ति के लिए जाएं
    - v को विज़िटेड के रूप में चिह्नित करें
    - v को nl के अंत में डालें
- l := nl
-1 लौटाएं

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

उदाहरण

class Solution:
    def solve(self, graph, target):
        visited = set()
        l = [target]
        length = 0
        while l:
            length += 1
            nl = []
            for u in l:
                for v in graph[u]:
                    if v == target:
                        return length
                    if v in visited:
                        continue
                    visited.add(v)
                    nl.append(v)
            l = nl
        return -1

ob = Solution()
graph = [[1, 4], [2], [3], [0, 1], []]
target = 3
print(ob.solve(graph, target))

इनपुट

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