Ta sẽ xét quá trình ngược lại: Ban đầu, không có cây cầu nào nối giữa các hòn đảo. Sau đó, các cây cầu m, m - 1, . . . , 1 lần lượt được xây dựng. Sau khi xây dựng mỗi cây cầu, hãy tính độ bất tiện (số cặp đảo không có đường đi trực tiếp đến nhau).
Để giải bài toán này, ta sẽ sử dụng cấu trúc dữ liệu disjoint-set union (DSU). Với mỗi thành phần liên thông, ta cần lưu trữ thêm số đỉnh trong thành phần liên thông đó. Ban đầu, độ bất tiện bằng 0. Khi thêm một cạnh nối hai thành phần liên thông khác nhau, gọi x và y lần lượt là số đỉnh trong từng thành phần liên thông. Khi đó, độ bất tiện sẽ giảm đi C^{2}_{x+y} - C^{2}_x - C^{2}_y (C^{2}_n là tổ hợp chập 2 của n, tương ứng với số cặp đỉnh trong một thành phần liên thông gồm n đỉnh).
Các bạn có thể tham khảo thêm về DSU tại bài viết sau: http://vnoi.info/wiki/algo/data-structures/disjoint-set
Độ phức tạp: O(n log n) hoặc O(n\alpha(n)) (với \alpha (n) là nghịch đảo hàm Ackermann, có thể xem như hằng số), tùy vào cách cài đặt DSU.