--- author: little tags: Thành phố trung tâm title: Thành phố trung tâm Solution --- $\Huge\text{Thành phố trung tâm Solution}$ ------- :::info 📌 Tags: `dfs` ✍️ Writer: little 📋 Content: [TOC] ::: ----- ## Thuật toán Tính mảng $low$ và mảng $num$ giống như thuật toán tìm khớp và cầu. Khi ta thực hiện việc tính $2$ mảng đó ta cũng sẽ lưu lại $1$ cái cây $Dfs$ luôn. Gọi $cur$ là số lượng thành phần liên thông của đồ thị ban đầu. Thì khi ta xét từng đỉnh trên cây $Dfs$ vừa lưu, ta kiểm tra xem nếu như loại bỏ đỉnh này đi thì tất cả có bao nhiêu thành phần liên thông? Ta sẽ đếm số lượng thành phần liên thông mới bằng cách xét từng đỉnh $v$ là con trực tiếp của đỉnh $u$ hiện tại, nếu như $low_v \ge num_u$ thì tức là các đỉnh nằm trong cây con gốc $v$ không có cạnh nối nào đến các đỉnh nằm ngoài cây con gốc $v$ cả (đồng nghĩa với việc số lượng thành phần liên thông được tăng thêm $1$). Sau khi đếm được số lượng thành phần liên thông sau khi loại bỏ đỉnh $u$ rồi thì ta cập nhật kết quả. Lưu ý là đồ thị ban đầu có thể là đa đồ thì, tức là có nhiều thành phân liên thông khác nhau nên các bạn phải xử lí thêm trường hợp này nhé. ---- Tham khảo code ở [đây](https://ideone.com/ClxI7U)