Как из компонент сильной связности построить конденсацию (граф компонент) без кратных рёбер?
У меня уже есть массив comp[v] — номер SCC каждой вершины (нашёл Тарьяном). Теперь нужно построить конденсацию: граф, где вершины — это компоненты, и есть ребро из компоненты A в B, если в исходном графе было ребро из вершины A-компоненты в вершину B-компоненты. Как это сделать и убрать кратные рёбра аккуратно?
2 ответа
Конденсация — это всегда ориентированный ациклический граф (DAG): внутри SCC всё взаимно достижимо, между разными SCC циклов быть не может (иначе они слились бы в одну). Это и делает конденсацию полезной — на DAG считают topsort, DP, достижимость.
Строим за один проход по рёбрам: для каждого ребра (v,u) исходного графа, если comp[v] != comp[u], добавляем ребро comp[v] -> comp[u]. Кратные рёбра убираем через множество пар:
int k = scc_cnt; // число компонент
vector<set<int>> cg(k); // или vector<vector<int>> + дедуп потом
for (int v = 0; v < n; v++)
for (int u : g[v])
if (comp[v] != comp[u])
cg[comp[v]].insert(comp[u]);
Сложность O((V+E)·log) из-за set. Если рёбер много, дешевле собрать пары в вектор, отсортировать и удалить дубликаты — O(E log E) без логарифма на каждую вставку:
vector<pair<int,int>> es;
for (int v = 0; v < n; v++)
for (int u : g[v]) if (comp[v]!=comp[u]) es.push_back({comp[v],comp[u]});
sort(es.begin(), es.end());
es.erase(unique(es.begin(), es.end()), es.end());
Память O(V+E).
Важный нюанс про ориентацию рёбер конденсации в зависимости от того, как пронумерованы SCC. У Тарьяна компоненты закрываются в обратном топологическом порядке: если comp[v] < comp[u], то почти наверняка ребро идёт «назад» по нумерации. Если вам нужен прямой топологический порядок DAG-а конденсации (для DP по стокам/истокам), проще:
- либо инвертировать номера:
comp[v] = scc_cnt - 1 - comp[v], - либо явно сделать топсорт уже на построенной конденсации.
Классическое применение — задача 2-SAT: строим граф импликаций, ищем SCC, и переменная истинна, если её SCC в топологическом порядке конденсации идёт позже SCC её отрицания. Так что направление и порядок номеров — не мелочь.