โปรแกรมหาขอบที่ตัดการเชื่อมต่อกราฟใน Python

สมมติว่าเราได้รับกราฟแบบไม่ระบุทิศทางซึ่งแสดงเป็นรายการที่อยู่ติดกัน โดยที่ graph[i] แทนโหนดเพื่อนบ้านของโหนด i เราต้องหาจำนวนขอบที่ตรงตามเงื่อนไขต่อไปนี้

หากเอาขอบออก กราฟจะขาดการเชื่อมต่อ

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

แล้วผลลัพธ์จะเป็น 1

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน dfs() นี้จะใช้เวลาก่อน d

  • ตอบ :=อนันต์

  • dep[curr] :=d

  • สำหรับแต่ละ adj ในกราฟ[curr] ทำ

    • ถ้า pre เหมือนกับ adj แล้ว

      • ทำซ้ำต่อไปโดยไม่ต้องทำตามขั้นตอนอื่น

    • ถ้า dep[adj] ไม่เหมือนกับ -1 ดังนั้น

      • ans :=ขั้นต่ำของ ans, dep[adj]

    • มิฉะนั้น

      • ans :=ขั้นต่ำของ ans, dfs(adj, curr, d + 1)

  • ถ้า d> 0 และ d <=ans แล้ว

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

ผลลัพธ์

1