पायथन में ग्राफ़ को डिस्कनेक्ट करने वाले किनारों का पता लगाने का कार्यक्रम

मान लीजिए कि हमें एक अप्रत्यक्ष ग्राफ प्रदान किया गया है जिसे आसन्न सूची के रूप में दर्शाया गया है, जहां ग्राफ [i] नोड i के पड़ोसी नोड्स का प्रतिनिधित्व करता है। हमें किनारों की संख्या ज्ञात करनी है जो निम्नलिखित शर्त को पूरा करती है।

यदि किनारे को हटा दिया जाता है, तो ग्राफ़ डिस्कनेक्ट हो जाता है।

So, if the input is like graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
],

तो आउटपुट 1 होगा।

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

फ़ंक्शन dfs () को परिभाषित करें। यह कर्ट, प्री, डी
. लेगा
- उत्तर:=अनंत
- dep[curr] :=d
- ग्राफ़ में प्रत्येक adj के लिए[curr], करें
  - यदि पूर्व adj के समान है, तो
    - अन्य चरणों को निष्पादित किए बिना अगला पुनरावृत्ति जारी रखें
  - यदि dep[adj] −1 के समान नहीं है, तो
    - उत्तर :=न्यूनतम उत्तर, dep[adj]
  - अन्यथा,
    - उत्तर:=न्यूनतम उत्तर, dfs(adj, curr, d + 1)
- यदि d> 0 और d <=उत्तर, तो
  - पुन:=पुनः + 1
- वापसी उत्तर
अब, मुख्य फ़ंक्शन से फ़ंक्शन को dfs () कहते हैं।
dep :=−1 से आरंभ किए गए ग्राफ़ के आकार की एक सूची।
पुन:=0
dfs(0, −1, 0)
वापस लौटें

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

उदाहरण

class Solution:
   def solve(self, graph):
      dep = [−1] * len(graph)
      INF = int(1e9)
      self.re = 0
      def dfs(curr, pre, d):
         ans = INF
         dep[curr] = d
         for adj in graph[curr]:
            if pre == adj:
               continue
            if dep[adj] != −1:
               ans = min(ans, dep[adj])
            else:
               ans = min(ans, dfs(adj, curr, d + 1))
         if d > 0 and d <= ans:
            self.re += 1
         return ans
      dfs(0, −1, 0)
      return self.re
ob = Solution()
print(ob.solve(graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
]))

इनपुट

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