Lesson 37 — Thành phần liên thông mạnh (SCC)
Ba module tương tác cho đồ thị CÓ HƯỚNG:
Kosaraju (2 DFS + transpose),
Tarjan (1 DFS + low-link),
và Condensation (gộp SCC thành DAG siêu đỉnh).
Đồ thị mẫu dùng chung: 0→1→2→0, 2→3, 3→4→5→3, 6→5, 6→7→6 — đáp án 3 SCC: {0,1,2}, {3,4,5}, {6,7}.
1. Kosaraju animator 2 DFS + transpose · O(V+E)
Bấm Bước tiếp để chạy 3 pha: (1) DFS lần 1 ghi finish order vào stack, (2) transpose (đảo mọi cạnh), (3) DFS lần 2 trên Gᵀ theo finish giảm dần — mỗi cây DFS tô một màu SCC.
chưa thăm
đang DFS
SCC #1
SCC #2
SCC #3
Bấm "Bước tiếp" để bắt đầu pha 1 (DFS lần 1).
Finish stack (pop từ phải): []
Pha hiện tại: —. Sau transpose, mũi tên trên hình đảo chiều.
2. Tarjan animator 1 DFS · disc/low/onStack
Một lần DFS. Theo dõi disc[u] (thời điểm thăm) và low[u] (đỉnh thấp nhất reach được). Khi low[u]==disc[u] → u là gốc SCC, pop stack tới u.
chưa thăm
trên stack (SCC đang mở)
SCC đã đóng
Bấm "Bước tiếp" để bắt đầu DFS từ đỉnh 0.
Tarjan stack: []
3. Condensation — gộp SCC thành DAG siêu đỉnh + topo
Sau khi biết các SCC, bóp mỗi SCC thành một siêu đỉnh. Cạnh liên cụm trở thành cạnh giữa siêu đỉnh → kết quả luôn là DAG. Bấm Thu gọn để xem.
Bấm "Thu gọn" để gộp các SCC.
—