---
Title : Sol bài 2
---
- Trước hết ta sẽ sort lại danh sách cạnh theo $w$ tăng dần và chặt nhị phân trên đó
- Với những cạnh có vị trí $\leq mid$ chúng ta sẽ thêm vào đồ thị
- Bây giờ bài toán chúng ta cần giải sẽ là cho một đồ thị có hướng, hãy xác định xem có tồn tại một đường đi từ ${u_i} \rightarrow {v_i}$ hay không
- Để có thể giải bài toán này ta sẽ nén đồ thị thành các thành phần liên thông mạnh để dễ xử lí
- Ta có mảng bool $reachable_{i,j} = true$ nếu chúng ta có thể có thể đến thành phần liên thông thứ $j$ khi bắt đầu đi ở thành phần liên thông thứ $i$ (kể cả chính nó)
- Để có thể xây mảng $reachable$ ta sẽ duyệt các thành phần liên thông mạnh theo thứ tự toposort đảo ngược, nếu có cạnh nối giữa hai thành phần liên thông mạnh $i,j$ thì $reachable_i = reachable_i$ $OR$ $reachable_j$
- Đáp án sau khi chúng ta chặt nhị phân sẽ là $w_{ans}$
- Lúc này độ phức tạp của chúng ta sẽ là $O((n ^ 2 + k) \times \log M)$ vì có $\log M$ lần kiểm tra và mỗi $n ^ 2 + k$ là chi phí kiểm tra cho mỗi lần chặt
Để có thể tối ưu hơn nữa ta sẽ lưu $n$ mảng $reachable$ dưới dạng bitset
(https://codeforces.com/blog/entry/71076)

Code mẫu cài đặt

vector<int> v;
//Gán kích thước và giá trị ngẫu nhiên cho v
for (int i = 1; i <= v.size(); i++){
    cout << v[i] << ' ';
}