পাইথনে গ্রাফ সংযোগ বিচ্ছিন্ন করে এমন প্রান্তগুলি খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি অনির্দেশিত গ্রাফ দেওয়া হয়েছে যা একটি সংলগ্ন তালিকা হিসাবে উপস্থাপন করা হয়েছে, যেখানে গ্রাফ[i] নোড i এর প্রতিবেশী নোডগুলিকে প্রতিনিধিত্ব করে। নিচের শর্ত পূরণ করে এমন প্রান্তের সংখ্যা আমাদের খুঁজে বের করতে হবে।

প্রান্তটি সরানো হলে, গ্রাফটি সংযোগ বিচ্ছিন্ন হয়ে যায়।

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

তাহলে আউটপুট হবে 1.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি curr, pre, d

  লাগবে

  • উত্তর :=অসীম

  • dep[curr] :=d

  • গ্রাফ[curr]-এ প্রতিটি adj-এর জন্য, do

    • যদি pre-এর মত adj হয়, তাহলে

      • অন্যান্য ধাপগুলি সম্পাদন না করে পরবর্তী পুনরাবৃত্তি চালিয়ে যান

    • যদি dep[adj] −1 এর মত না হয়, তাহলে

      • উত্তর :=সর্বনিম্ন উত্তর, dep[adj]

    • অন্যথায়,

      • উত্তর :=সর্বনিম্ন উত্তর, dfs(adj, curr, d + 1)

  • যদি d> 0 এবং d <=ans, তাহলে

    • re :=re + 1

  • উত্তর ফেরত দিন

• এখন, প্রধান ফাংশন থেকে ফাংশন dfs().

  কল করুন

• dep :=−1 দিয়ে শুরু করা গ্রাফের আকারের একটি তালিকা।

• re :=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]
]

আউটপুট

1