Обнаружение цикла в неориентированном графе: DFS с родителем vs DSU — что надёжнее?
Нужно просто проверить, есть ли в неориентированном графе хоть один цикл. Знаю два подхода: DFS с передачей родителя и через систему непересекающихся множеств. В чём подвох DFS с родителем при кратных рёбрах? И какой подход лучше?
2 ответа
DFS с родителем. Цикл есть, если при обходе встретили уже посещённую вершину, не являющуюся родителем по дереву DFS:
vector<int> g[N]; vector<bool> used;
bool dfs(int v, int parent) {
used[v] = true;
for (int u : g[v]) {
if (!used[u]) { if (dfs(u, v)) return true; }
else if (u != parent) return true; // обратное ребро = цикл
}
return false;
}
Подвох с кратными рёбрами: если между v и u два параллельных ребра, бан по вершине-родителю (u != parent) ошибочно сочтёт второе ребро «ребром в родителя» и пропустит цикл (а два параллельных ребра — это уже цикл!). Если в графе возможны кратные рёбра — банить надо по индексу ребра, по которому вошли, как в задачах про мосты. Петля (v–v) — тоже цикл, обрабатывается отдельно.
DSU. Идём по рёбрам; если концы ребра уже в одной компоненте — ребро замыкает цикл:
DSU d(n);
for (auto [a, b] : edges)
if (!d.unite(a, b)) { /* цикл найден */ }
DSU кратных рёбер не боится по своей природе: второе ребро между уже объединёнными a,b сразу даёт unite==false. Сложность DFS — O(V+E), DSU — O(E·α(V)).
Что лучше: DSU надёжнее (нет проблем с кратными рёбрами и рекурсией/стеком) и проще, если граф дан списком рёбер. DFS удобнее, если ещё нужно восстановить сам цикл.
Дополню про восстановление цикла через DFS (DSU цикл находит, но не выдаёт его вершины напрямую). Храним стек/родителей; при нахождении обратного ребра (v→u, где u — предок) поднимаемся по par[] от v до u, собирая вершины:
int par[N];
// ... при обратном ребре v->u:
vector<int> cyc; for (int x = v; x != u; x = par[x]) cyc.push_back(x);
cyc.push_back(u);
И напоминание про разницу с ориентированным графом: там «посещён и не родитель» НЕ работает — нужны три цвета (белый/серый/чёрный), и цикл = ребро в серую (на стеке рекурсии) вершину. Не переносите неориентированный критерий на ориентированный граф — это частая ошибка.