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

मान लीजिए, हमें एक ग्राफ दिया गया है जिसमें n शीर्ष हैं जो 0 से n-1 तक क्रमांकित हैं। ग्राफ अनिर्देशित है और प्रत्येक किनारे का एक भार है। ग्राफ में तीन प्रकार के भार हो सकते हैं और प्रत्येक भार एक विशेष कार्य को दर्शाता है। दो लोग हैं जो ग्राफ को पार कर सकते हैं, अर्थात् जैक और केसी। जैक ग्राफ को पार कर सकता है यदि किनारे का भार 1 है, केसी ग्राफ को पार कर सकती है यदि भार 2 है, और दोनों ग्राफ को पार कर सकते हैं यदि किनारे का भार 3 है। हमें ग्राफ को जैक और केसी दोनों के लिए पारगम्य बनाने के लिए आवश्यक किनारों को हटाना है। हम ग्राफ को पारगम्य बनाने के लिए हटाए जाने वाले किनारों की संख्या वापस करते हैं, या -1 वापस करते हैं यदि इसे पारगम्य नहीं बनाया जा सकता।

इसलिए, यदि इनपुट इस तरह है

और n =5; तो आउटपुट -1 होगा

ग्राफ को एक किनारा हटाकर दोनों के लिए पारगम्य नहीं बनाया जा सकता। इसलिए, उत्तर -1 है।

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

एक फ़ंक्शन find() परिभाषित करें। यह val लेगा
- यदि val, root[val] के समान नहीं है, तो
  - root[val] := find(root[val])
- root[val] वापस करें
एक फ़ंक्शन union() परिभाषित करें। यह val1, val2 लेगा
- val1 := find(val1)
- val2 := find(val2)
- यदि val1, val2 के समान है, तो
  - 0 वापस करें
- root[val1] := val2
- 1 वापस करें
res := 0
edge1 := 0
edge2 := 0
root := 0 से n + 1 तक की रेंज वाली एक नई सूची
e में प्रत्येक किनारे (u, v), और उसके भार w के लिए, करें
- यदि u, 3 के समान है, तो
  - यदि union(v, w) शून्येतर है, तो
    - edge1 := edge1 + 1
    - edge2 := edge2 + 1
  - अन्यथा,
    - res := res + 1
root0 := root[इंडेक्स 0 से अंत तक]
e में प्रत्येक किनारे (u, v), और उसके भार w के लिए, करें
- यदि u, 1 के समान है, तो
  - यदि union(v, w) शून्येतर है, तो
    - edge1 := edge1 + 1
  - अन्यथा,
    - res := res + 1
root := root0
e में प्रत्येक किनारे (u, v), और उसके भार w के लिए, करें
- यदि u, 2 के समान है, तो
  - यदि union(v, w) शून्येतर है, तो
    - edge2 := edge2 + 1
  - अन्यथा,
    - res := res + 1
यदि edge1, edge2 के समान है और n - 1 तो res वापस करें
अन्यथा, -1 वापस करें

उदाहरण

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

def solve(n, e):
    def find(val):
        if val != root[val]:
            root[val] = find(root[val])
        return root[val]
    def union(val1, val2):
        val1, val2 = find(val1), find(val2)
        if val1 == val2: return 0
        root[val1] = val2
        return 1
    res = edge1 = edge2 = 0
    root = list(range(n + 1))
    for u, v, w in e:
        if u == 3:
            if union(v, w):
                edge1 += 1
                edge2 += 1
            else:
                res += 1
    root0 = root[:]
    for u, v, w in e:
        if u == 1:
            if union(v, w):
                edge1 += 1
            else:
                res += 1
    root = root0
    for u, v, w in e:
        if u == 2:
            if union(v, w):
                edge2 += 1
            else:
                res += 1
    return res if edge1 == edge2 == n - 1 else -1

print(solve(5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]))

इनपुट

Input: 5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]

आउटपुट

-1