पायथन में उन एज को ज्ञात करने का प्रोग्राम जो ग्राफ को डिस्कनेक्ट करते हैं

मान लीजिए हमें एक अनडायरेक्टेड ग्राफ दिया गया है जिसे एडजेसेंसी लिस्ट के रूप में दर्शाया गया है, जहां graph[i] नोड i के पड़ोसी नोड्स हैं। हमें उन एज की संख्या ज्ञात करनी है जिन्हें हटाने पर ग्राफ डिस्कनेक्ट हो जाता है (ब्रिज एज)।

उदाहरण के लिए, दिए गए ग्राफ के लिए आउटपुट 1 होगा।

एल्गोरिदम (DFS - टार्जन का एल्गोरिदम)

• dfs(curr, pre, d) फ़ंक्शन परिभाषित करें:
  • ans := INF, dep[curr] := d
  • प्रत्येक adj in graph[curr] के लिए:
    • यदि pre == adj, तो जारी रखें
    • यदि dep[adj] != -1, तो ans = min(ans, dep[adj])
    • अन्यथा ans = min(ans, dfs(adj, curr, d+1))
  • यदि d > 0 और d <= ans, तो re++ (ब्रिज मिला)
  • ans वापस करें
• मुख्य फ़ंक्शन से:
  • dep := [-1]*len(graph), re := 0
  • dfs(0, -1, 0) कॉल करें
  • re वापस करें

उदाहरण

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]]

आउटपुट

1