Можно ли DSU использовать для проверки, образует ли набор рёбер цикл (детект цикла в неориентированном графе)?
Дан неориентированный граф рёбрами, хочу понять, есть ли в нём цикл, без полного DFS. Кажется, DSU это умеет «на лету» при добавлении рёбер. Как именно, и работает ли это для ориентированного графа тоже?
2 ответа
Да: добавляя рёбра по одному, при попытке соединить ребром (u,v) две вершины, которые уже в одной компоненте, мы замыкаем цикл. То есть цикл существует ⇔ хотя бы одно unite вернуло false (концы уже связаны).
bool hasCycle(int n, vector<pair<int,int>>& edges){
DSU dsu(n);
for (auto& [u, v] : edges)
if (!dsu.unite(u, v)) return true; // u и v уже связаны -> цикл
return false;
}
Сложность — O((n+m)·α(n)), память O(n). Это ровно тот же критерий, что в Краскале отсекает «лишние» рёбра. Для леса/остова удобно: если ни одно ребро не дало false, граф ацикличен (лес).
Важно: только для НЕориентированных графов. В ориентированном DSU не различает направления и не ловит ориентированные циклы — там нужен DFS с цветами (white/gray/black) или Kahn (топосорт): если топологическая сортировка невозможна, есть ориентированный цикл. DSU для ориентированного детекта цикла неприменим.
Нюанс с кратными рёбрами и петлями: петля (u,u) формально — цикл длины 1, и unite(u,u) вернёт false, так что код выше её поймает как «цикл» — обычно это и хотят. А вот два параллельных ребра между u и v: первое сольёт компоненты, второе даст false → код скажет «цикл». Это корректно для мультиграфа (две параллельные дуги образуют цикл длины 2), но если по условию кратные рёбра надо игнорировать, дедуплицируйте рёбра заранее.