Двусвязные компоненты по рёбрам: как сжать граф в дерево, разрезая по мостам?
Нашёл все мосты в неориентированном графе. Теперь хочу разбить граф на компоненты рёберной двусвязности (между любыми двумя вершинами компоненты есть два рёберно-непересекающихся пути) и получить «дерево мостов» — где компоненты это вершины, а мосты соединяют их. Как это построить из найденных мостов?
2 ответа
Компоненты рёберной двусвязности (2-edge-connected components) — это в точности то, что остаётся «слитным», если мысленно удалить все мосты. Внутри такой компоненты любые два пути можно сделать рёберно-непересекающимися; мосты — единственные рёбра, чьё удаление рвёт граф.
Алгоритм:
- Найти все мосты (tin/low, бан по индексу ребра).
- Запустить DFS/DSU, объединяя вершины только по не-мостовым рёбрам. Получившиеся группы — это 2ECC.
- Стянуть каждую компоненту в вершину; мосты между компонентами дают рёбра. Результат — дерево (мосты не лежат на циклах, значит сжатый граф ацикличен и связен в пределах исходной компоненты).
// после того как isBridge[id] заполнен:
DSU d(n);
for (each edge id with endpoints (a,b))
if (!isBridge[id]) d.unite(a, b); // сливаем всё, кроме мостов
// d.find(v) = номер 2ECC вершины v
// строим дерево мостов:
vector<pair<int,int>> tree;
for (each bridge id with endpoints (a,b))
tree.push_back({ d.find(a), d.find(b) });
Почему дерево: в дереве мостов V' = число 2ECC, рёбер ровно (число мостов) = V'−1 в пределах связной компоненты исходного графа — классический признак дерева.
Сложность O(V+E) (мосты) + O(E·α) (сжатие). Память O(V+E).
Это мощный приём: задачи «минимум мостов на пути», «сколько рёбер удалить, чтобы разорвать связь» на дереве мостов решаются как задачи на обычном дереве (LCA, и т.п.).
Не путайте с компонентами вершинной двусвязности (2-vertex-connected / biconnected components) — там разрезают по точкам сочленения, и одна вершина-сочленение может принадлежать нескольким блокам. Структура там — «дерево блоков и точек сочленения» (block-cut tree), и строится оно иначе: через стек рёбер во время DFS, выгружая блок при low[u] >= tin[v].
Коротко: 2ECC ↔ мосты ↔ DSU по не-мостам ↔ дерево мостов (просто). 2VCC ↔ точки сочленения ↔ стек рёбер ↔ block-cut tree (сложнее, вершины делятся между блоками). Чётко понимайте, какая двусвязность нужна в задаче — рёберная или вершинная, иначе соберёте не ту структуру.