Мосты в неориентированном графе через tin/low — почему важно не идти назад по ребру в родителя?
Ищу мосты (ребра, удаление которых увеличивает число компонент связности). Использую DFS с tin/low. Видел условие low[u] > tin[v] для ребра-моста, но у меня всё ломается, когда есть кратные рёбра и когда возвращаюсь по ребру в родителя. Как правильно обработать ребро в родителя?
2 ответа
Мост — ребро (v,u) дерева DFS, такое что из поддерева u нет обратного ребра в v или выше. Формально: low[u] > tin[v], где low[u] — минимальный tin, достижимый из поддерева u (через дерево + обратные рёбра).
Ключ — корректно учитывать ребро в родителя. По дереву мы пришли в u из v по одному конкретному ребру; идти по нему обратно нельзя. Но если между v и u кратное ребро, второе такое ребро — уже не «то самое», и по нему обновлять low можно (оно делает ребро не-мостом). Поэтому передаём не родителя-вершину, а индекс ребра, по которому пришли:
int timer = 0;
vector<int> tin, low;
vector<vector<pair<int,int>>> g; // g[v] = {сосед, индекс ребра}
vector<bool> isBridge; // по индексу ребра
void dfs(int v, int pe) { // pe — индекс ребра, по которому вошли
tin[v] = low[v] = timer++;
for (auto [u, id] : g[v]) {
if (id == pe) continue; // не идём назад по ТОМУ ЖЕ ребру
if (tin[u] != -1) { // обратное ребро
low[v] = min(low[v], tin[u]);
} else {
dfs(u, id);
low[v] = min(low[v], low[u]);
if (low[u] > tin[v]) isBridge[id] = true;
}
}
}
Почему именно индекс ребра, а не вершина-родитель: при parent != u сравнении два параллельных ребра v–u оба «забанятся», и алгоритм решит, что моста нет там, где он есть, или наоборот. Бан по индексу ребра банит ровно одно вошедшее ребро.
Сложность O(V+E), память O(V+E). Не забудьте tin.assign(n,-1) и запуск из каждой непосещённой вершины.
Частая альтернатива бану по индексу — считать, сколько раз встретился родитель: разрешить одно обратное ребро в родителя и банить только первое. Это работает, но именно вариант «через индекс ребра» надёжнее и обобщается на точки сочленения.
И строгое неравенство low[u] > tin[v] (а не >=) принципиально: при low[u] == tin[v] из поддерева есть обратное ребро ровно в v, значит ребро лежит на цикле — не мост. Для точек сочленения условие другое (low[u] >= tin[v] для не-корня), так что не перепутайте знаки между мостами и точками сочленения.