यह पता लगाने के लिए कार्यक्रम कि क्या पायथन में सभी के द्वारा ग्राफ़ को ट्रैवर्स किया जा सकता है

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

तो, अगर इनपुट पसंद है

और एन =5; तो आउटपुट -1

. होगा

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

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

फ़ंक्शन ढूंढें() को परिभाषित करें। इसमें वैल लगेगा
- अगर वैल रूट [वैल] के समान नहीं है, तो
  - रूट [वैल]:=ढूंढें (रूट [वैल])
- वापसी रूट[वैल]
एक फ़ंक्शन यूनियन () को परिभाषित करें। इसमें वैल1, वैल2 लगेगा
- val1:=ढूंढें(val1)
- val2 :=find(val2)
- अगर वैल1 वैल2 के समान है, तो
  - वापसी 0
- रूट [वैल 1]:=वैल 2
- वापसी 1
रेस :=0
बढ़त1 :=0
धार2 :=0
रूट :=0 से n + 1 तक की एक नई सूची
प्रत्येक किनारे के लिए (यू, वी), और इसका वजन ई में डब्ल्यू, करो
- अगर आप 3 के समान हैं, तो
  - यदि संघ (v, w) गैर-शून्य है, तो
    - एज1 :=edge1 + 1
    - एज2 :=एज2 + 1
  - अन्यथा,
    - रेस :=रेस + 1
root0 :=root[सूचकांक 0 से अंत तक]
प्रत्येक किनारे के लिए (यू, वी), और इसका वजन ई में डब्ल्यू, करो
- अगर आप 1 के समान हैं, तो
  - यदि संघ (v, w) गैर-शून्य है, तो
    - एज1 :=edge1 + 1
  - अन्यथा,
    - रेस :=रेस + 1
जड़ :=root0
प्रत्येक किनारे के लिए (यू, वी), और इसका वजन ई में डब्ल्यू, करो
- अगर आप 2 के समान हैं, तो
  - यदि संघ (v, w) गैर-शून्य है, तो
    - एज2 :=एज2 + 1
  - अन्यथा,
    - रेस :=रेस + 1
अगर एज1 एज 2 और n - 1 के समान है तो रेज लौटाएं
अन्यथा, वापसी -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