Graph Theory37 sections · 1633 units
Open in Course

Pattern - Offline Queries

Reordering Time

Sometimes you are given a static graph and many questions like: "Are nodes uu and vv connected using only edges with weight W\leq W?" DSU cannot answer this directly because it does not support "undo" or filtering by weight.

The trick: process queries offline. Sort edges by weight. Sort queries by weight. Process both in increasing weight order. When you reach a query's weight threshold, all relevant edges are already unioned.