Graph Theory37 sections · 1633 units
Open in Course

Pattern - The Reverse Time Trick

Destruction is hard

Many problems ask you to destroy or remove edges and count components. DSU cannot remove edges. It can only add.

The trick: process in reverse! Start from the final state (everything removed), then add edges backward. Deletions become insertions.

This "reverse time" approach converts decremental problems into incremental ones that DSU handles naturally. Store answers in an array as you add edges, then reverse the array to get the original deletion order.