পাইথনে গ্রাফের ব্রিজ এজ বা বিচ্ছিন্নকারী প্রান্ত নির্ণয়

একটি অনির্দেশিত গ্রাফ অ্যাডজেসেন্সি লিস্ট আকারে দেওয়া আছে। এমন প্রান্তের সংখ্যা বের করতে হবে যেগুলো সরালে গ্রাফটি বিচ্ছিন্ন হয়ে যায়।

উদাহরণ: graph = [[0,2],[0,4],[1,2,3],[0,3,4],[4],[3],[2]] হলে আউটপুট ১।

সমাধানের ধাপসমূহ

DFS ব্যবহার করে ডিসকভারি টাইম এবং লো ভ্যালু গণনা করুন
dfs(curr, pre, d) ফাংশন সংজ্ঞায়িত করুন
প্রতিটি আ ڈজেসেন্ট নোডের জন্য লো ভ্যালু আপডেট করুন
যদি d > 0 এবং d <= ans হয় তবে সেটা ব্রিজ, কাউন্ট বাড়ান
সর্বোচ্চ ব্রিজ সংখ্যা ফেরত দিন

উদাহরণ কোড

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