Chương trình tìm các cạnh cầu (bridge) làm ngắt liên thông đồ thị trong Python

Cho đồ thị vô hướng dạng danh sách kề graph[i] là các đỉnh kề của i. Tìm số cạnh mà nếu xóa sẽ làm đồ thị ngắt liên thông (cầu/bridge).

Ví dụ: graph=[[0,2],[0,4],[1,2,3],[0,3,4],[4],[3],[2]] → 1.

Giải thuật (DFS Tarjan tìm Bridge - Lowlink)

1. dep[u] = độ sâu DFS. ans = min dep[v] của các đỉnh vachable từ u (kể cả qua back-edge).
2. DFS(curr, pre, d):
   • dep[curr] = d, ans = INF.
   • Với mỗi adj kề:
     • Bỏ qua pre.
     • Nếu dep[adj] != -1 (back-edge): ans = min(ans, dep[adj]).
     • Ngược lại (tree-edge): ans = min(ans, dfs(adj, curr, d+1)).
   • Nếu d > 0 and d <= ans: cạnh (pre, curr) là cầu → re++.
   • Trả về ans.

Ví dụ minh họa

class Solution:
    def solve(self, graph):
        n = len(graph)
        dep = [-1] * n
        INF = 10**9
        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()
graph = [[0,2],[0,4],[1,2,3],[0,3,4],[4],[3],[2]]
print(ob.solve(graph))  # Output: 1

Đầu vào / Đầu ra

Input: [[0,2],[0,4],[1,2,3],[0,3,4],[4],[3],[2]]

Output: 1