Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं


मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं ताकि ग्राफ में प्रत्येक किनारा {u,v} का एक नोड u A में और दूसरा नोड v B में हो।

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

पायथन में जांचें कि दिया गया ग्राफ द्विभाजित है या नहीं

तो आउटपुट होगा True, [0,4] सेट A में हैं और [1,2,3] सेट B में हैं, और सभी किनारे A से B या B से A हैं, A से A या B से B नहीं।

हल करने के चरण

  • एक फ़ंक्शन dfs() परिभाषित करें। यह source लेगा।
  • ग्राफ[source] में प्रत्येक शीर्ष के लिए:
    • यदि color[vertex] -1 के समान नहीं है, तो:
      • यदि color[vertex], color[source] के समान है, तो result[0] := False और लौटें।
      • अगले पुनरावृत्ति के लिए जारी रखें।
    • color[vertex] := 1 - color[source]
    • dfs(vertex)
  • मुख्य विधि से:
    • n := arr का आकार।
    • graph := 0 से n-1 शीर्षों के लिए खाली आसन्न सूची।
    • i को 0 से n तक:
      • arr[i] में प्रत्येक j के लिए:
        • i को graph[j] में डालें।
        • j को graph[i] में डालें।
    • color := आकार n की सूची, -1 से भरी हुई।
    • result := एक True मान वाली सूची।
  • i को 0 से n तक:
    • यदि color[i] -1 के समान है, तो dfs(i)।
  • result[0] लौटाएं।

उदाहरण

from collections import defaultdict
class Solution:
    def solve(self, arr):
        n = len(arr)
        graph = [set() for i in range(n)]
        for i in range(n):
            for j in arr[i]:
                graph[j].add(i)
                graph[i].add(j)
        color = [-1] * n
        result = [True]
        def dfs(source):
            for child in graph[source]:
                if color[child] != -1:
                    if color[child] == color[source]:
                        result[0] = False
                        return
                    continue
                color[child] = 1 - color[source]
                dfs(child)
        for i in range(n):
            if color[i] == -1:
                dfs(i)
        return result[0]

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

इनपुट

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

आउटपुट

True
  1. दिए गए ब्लॉक्स की सूची x = y रेखा पर सममित है या नहीं जांचने का पायथन प्रोग्राम दिए गए ब्लॉक्स की सूची x = y रेखा पर सममित है या नहीं जांचने का पायथन प्रोग्राम

    मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है। और यह वर्ग ब्लॉक्स की ऊंचाई को दर्शाता है, हमें जांचना है कि क्या आकृति y = x रेखा पर सममित है या नहीं। उदाहरण के लिए, यदि इनपुट nums = [7, 5, 3, 2, 2, 1, 1] है, तो आउटपुट True होगा। इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे: i := 0 j

  1. Python में दिया गया ट्री सममित ट्री है या नहीं, इसकी जांच करने का प्रोग्राम Python में दिया गया ट्री सममित ट्री है या नहीं, इसकी जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह जांचना है कि ट्री सममित ट्री है या नहीं। एक ट्री को सममित कहा जाएगा यदि यह उसके दर्पण छवि लेने पर समान हो। इन दो ट्री में से पहला सममित है, लेकिन दूसरा नहीं। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे। हम निम्नलिखित चरणों को रिकर्सिवली कॉल करे

  1. पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग कीवर्ड है या नहीं पायथन प्रोग्राम: जांचें कि दी गई स्ट्रिंग कीवर्ड है या नहीं

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक स्ट्रिंग दी गई है, हमें जांचना है कि यह स्ट्रिंग पायथन का कीवर्ड है या नहीं। कीवर्ड किसी भी भाषा द्वारा आरक्षित विशेष शब्द होते हैं जिनका विशिष्ट उपयोग होता है और उन्हें पहचानकर्ता के रूप में उपयोग नहीं किया जा सकता। यह जां