Một số ứng dụng nâng cao của cây DFS (phần 2)
III. Bài toán tìm thành phần liên thông mạnh - giải thuật Tarjan
1. Định nghĩa thành phần liên thông mạnh
Đối với đồ thị G=(V,E)G=(V, E)G=(V,E) có hướng, ta có ba định nghĩa về tính liên thông:
GGG được gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt (u,v)(u, v)(u,v), ta có uuu đến được vvv và vvv đến được uuu.
GGG được gọi là liên thông yếu (weakly connected) nếu...
Algorithm
Viblo
Viblo Algorithm
2221