ได้รับกราฟแบบไม่มีทิศทาง (adjacency list) หาจำนวน Bridge edges (ขอบที่ถ้าลบออกกราฟจะแยก component)
ตัวอย่าง
graph = [
[0, 2], [0, 4], [1, 2, 3], [0, 3, 4], [4], [3], [2]
]
Output: 1
แนวทางแก้ปัญหา
Tarjan's Algorithm (DFS + Low-link values):
dep[u]= discovery time (depth)low[u]= min discovery time ที่ถึงได้จาก u ผ่าน tree edges + back edges- Edge (u,v) เป็น bridge ถ้า
low[v] > dep[u](v เป็นลูกของ u ใน DFS tree)
การใช้งาน (Python)
class Solution:
def solve(self, graph):
n = len(graph)
dep = [-1] * n
self.bridges = 0
INF = 10**9
def dfs(u, parent, depth):
dep[u] = depth
low = depth
for v in graph[u]:
if v == parent:
continue
if dep[v] != -1:
# Back edge
low = min(low, dep[v])
else:
# Tree edge
child_low = dfs(v, u, depth + 1)
low = min(low, child_low)
# Check bridge
if depth < child_low:
self.bridges += 1
return low
dfs(0, -1, 0)
return self.bridges
# ทดสอบ
ob = Solution()
graph = [
[0, 2], [0, 4], [1, 2, 3], [0, 3, 4], [4], [3], [2]
]
print(ob.solve(graph)) # Output: 1
ความซับซ้อน
- Time Complexity: O(V + E)
- Space Complexity: O(V)
หมายเหตุ: โค้ดต้นฉบับมี logic ค่อนข้างสับสน รุ่นนี้เขียนใหม่ให้ชัดเจนตาม Tarjan มาตรฐาน
