Tutorial — Đánh Giá Nút Mạng

Chỉ số gián đoạn của một máy chủ $v$ phản ánh số lượng thành phần liên thông còn lại của đồ thị sau khi loại bỏ đỉnh $v$. Nếu $v$ không phải là điểm khớp, số thành phần liên thông còn lại luôn bằng $1$.

Trên cây DFS, một nhánh con của đỉnh $u$ gốc $v$ sẽ bị cô lập hoàn toàn khỏi phần còn lại của đồ thị sau khi xóa $u$ khi và chỉ khi từ cây con gốc $v$ không có cạnh ngược nào nối lên các đỉnh tổ tiên phía trên $u$. Điều này tương ứng với điều kiện mốc thời gian $low[v] \ge tin[u]$.

Sử dụng thuật toán DFS dựa trên thuật toán Tarjan để tính mảng $tin$ và $low$ cho toàn bộ đồ thị. Đếm số lượng đỉnh con $v$ của $u$ thỏa mãn $low[v] \ge tin[u]$ để xác định số thành phần liên thông tăng thêm cho từng đỉnh $u$, lưu ý xử lý riêng biệt cho đỉnh gốc của cây DFS.