Сегодня у нас интересная тема - мосты из теории графов
Определение
Мост - это ребро, при удалении которого связный граф распадается на две части. В контексте сетей такие рёбра представляют собой уязвимости: если такое соединение выйдет из строя, часть узлов окажется недоступной.
Идея
Прямой перебор всех рёбер с проверкой связности после удаления потребует O(m ^ 2) операций, что долго для больших графов.
Упростить задачу помогает обход в глубину (DFS). При обходе все рёбра можно разделить на два типа:
- прямые рёбра, по которым DFS переходит впервые;
- обратные рёбра, которые ведут к уже посещённым вершинам.
Обратные рёбра не могут быть мостами: если удалить такое ребро, то путь между вершинами останется через дерево обхода.
Значит, достаточно проверить только прямые рёбра. Наивная проверка каждого прямого ребра отдельно всё ещё требует O(n * m) времени. Но можно оптимизировать до O(n + m), используя дополнительную информацию, которую собираем в процессе DFS.
Введём для каждой вершины v:
h[v] - глубина вершины в дереве DFS;
d[v] - минимальная глубина, достижимая из поддерева v по обратным рёбрам.
Эти величины вычисляются рекурсивно во время обхода. Для прямого ребра v -> u условие того, что оно является мостом, выглядит так: h[v] < d[u].
Если условие выполняется, то из поддерева u нет обратного ребра, ведущего в v или выше - значит, ребро критическое. В противном случае существует обходной путь, и ребро мостом не является.
Код
const int maxn = 1e5;
bool used[maxn];
int h[maxn], d[maxn];
void dfs(int v, int p = -1) {
used[v] = true;
d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
for (int u : g[v]) {
if (u != p) {
if (used[u]) // если ребро обратное
d[v] = min(d[v], h[u]);
else { // если ребро прямое
dfs(u, v);
d[v] = min(d[v], d[u]);
if (h[v] < d[u]) {
// если нельзя другим путем добраться в v или выше,
// то ребро (v, u) - мост
}
}
}
}
}
Пишите в комментарии, что разобрать следующее 🦖
@postupashki_prog