Xét một đồ thị vô hướng ~G~ ban đầu gồm ~n~ đỉnh và không có cạnh nào. Xét truy vấn ~c, l, r, k~, với mỗi ~0\le x \le k~ ta nối cạnh giữa ~l+x~ và ~r+x~ với trọng số ~c~.

Đáp án sẽ là ~0~ nếu tồn tại hai đỉnh ~u~ và ~v~ mà tồn tại hai đường đi giữa hai đỉnh này có tính chẵn lẽ khác nhau, ngược lại gọi ~C~ là số thành phần liên thông thì đáp án là ~2^C~ (bạn đọc tự chứng minh).

Tất nhiên nếu ta thêm toàn bộ cạnh vào ~G~ sẽ rất chậm nên ta sẽ sử dụng DSU.

Duy trì ~\lceil \log_2n\rceil~ DSU, một cạnh ~u-v~ trên DSU thứ ~k~ có ý nghĩa là xâu con ~[u+2^k)~ bằng/ngược với xâu con ~[v+2^k)~.

Ta dễ dàng tách mỗi truy vấn thành nhiều nhất hai truy vấn có độ dài là một lũy thừa của ~2~.

Xét truy vấn ~c, l, r, k~ với ~k+1=2^x~, ta thêm cạnh giữa ~l~ và ~r~ trên DSU thứ ~x~. Nếu trước đó ~l~ và ~r~ chưa cùng thành phần liên thông trên DSU ~x~ thì ta đệ quy xét hai truy vấn con ~c, l, r, \frac{k}{2}~ và ~c, l + \frac{k}{2} + 1, r + \frac{k}{2}+1, \frac{k}{2}~.

Thuật toán này có độ phức tạp ~O((m + n\log_2n) \cdot X)~ với ~X~ là độ phức tạp của DSU, bởi vì mỗi DSU ta sẽ thực hiện phép ~\text{join}~ không quá ~n~ lần.