Зачем держать DSU отдельно, если связность можно проверять обходом — когда DSU реально выигрывает?
Если граф уже дан целиком, я могу один раз пробежать DFS/BFS и расставить компоненты за O(V+E). Зачем тогда вообще DSU? В каких ситуациях он принципиально лучше обхода?
2 ответа
DSU выигрывает там, где граф меняется во времени, и рёбра только добавляются (инкрементальная связность), либо где удобнее жадно сливать множества, а не строить явный граф.
- Динамика по добавлению рёбер: после каждого добавления нужно отвечать «связны ли X и Y» / «сколько компонент». DFS заставлял бы перестраивать всё за O(V+E) на каждый запрос — итого O(q·(V+E)). DSU отвечает за O(α(n)) на операцию, суммарно почти O(q+V+E).
- Краскал (MST): нет смысла строить граф и обходить — нужно лишь «в одной ли компоненте концы ребра».
- Слияние множеств по условию (объединить группы людей/предметов): DSU — естественная модель.
DFS/BFS лучше, когда граф статичен, нужен один проход, либо нужны вещи, которых DSU не умеет: фактические пути, расстояния, компоненты сильной связности, мосты, порядок обхода. DSU — это про «какие элементы в одном множестве» и только про добавление рёбер; удаление ребра онлайн он не умеет (нужны более тяжёлые структуры — Link-Cut Tree / Euler Tour Tree, либо офлайн через segment tree по времени).
Короче: статичный граф и пути → обход; растущая связность и слияния → DSU.
Добавлю частый практический кейс: офлайн-обработка удалений через обращение времени. Если в задаче рёбра только удаляются, разворачиваем порядок запросов — и удаления превращаются в добавления, которые DSU умеет. Обходом так не сделать. Это типичный трюк «решаем задачу с конца», и именно DSU делает его дешёвым.