Nguồn: https://beta.atcoder.jp/contests/arc065/tasks/arc065_b

Xét đồ thị chỉ gồm các tuyến đường bộ. Ta dùng DFS để đánh số các thành phần liên thông.

Gọi c1[u] là số thứ tự của thành phần liên thông chứa đỉnh u.

Tương tự, gọi c2[u] là số thứ tự của thành phần liên thông chứa đỉnh u, nếu xét đồ thị chỉ gồm các tuyến đường sắt.

Khi đó, hai thành phố u và v liên thông bằng đường bộ và liên thông bằng đường sắt khi và chỉ khi c1[u] = c1[v] và c2[u] = c2[v]

Ta có thể dùng cấu trúc dữ liệu map trong C++ (với mỗi khóa là một pair của giá trị c1 và c2 tương ứng với từng đỉnh) để thực hiện việc đếm trong độ phức tạp O(N log N).

Một cách khác là sắp xếp các đỉnh tăng dần theo c1, nếu bằng nhau thì tăng dần theo c2 và dùng hai con trỏ để thực hiện việc đếm.

Độ phức tạp của cách này cũng là ~O(N log N)~.