Продвинутый DFS

Время входа и выхода

Вспомним обычный поиск в глубину. Он рекурсивно обходит весь граф, и посещает каждую вершину ровно один раз. Посещенные вершины при этом отмечаются в массиве used.

Давайте его немного модифицируем, а именно, давайте сохраним в какой-нибудь массив, в каком порядке мы посещали вершины. Есть два способа это сделать - посчитать время входа DFS-а в каждую вершину и время выхода.

Давайте назовем массивы $\mathrm{t}\mathrm{i}\mathrm{n}$ и $\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}$, где $\mathrm{t}\mathrm{i}\mathrm{n}$ - время входа, а $\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}$ - время выхода из вершины.

Как их заполнить: давайте заведем таймер, отвечающий за время на текущий момент программы и будем обновлять информацию, когда заходим/выходим из вершины:

int timer = 0;

void dfs (int v) {
    tin[v] = timer++;
    for (int i = 0; i < g[v].size(); ++i) {
        if (!used[g[v][i]]) {
            dfs(g[v][i]);
    }
  }
  tout[v] = timer++;
}

Время входа или выхода пригождается во многих алгоритмах, давайте разберем несколько.

Топологическая сортировка

Задача о топологической сортировке графа звучит так:

Дан ориентированный граф, нужно расставить его вершины в массиве так, чтобы все ребра шли вправо по массиву.

Эта же задача очень часто встречается в реальной жизни. Например, у вас есть много зависимостей вида “в библиотеке А используется библиотека B”, и вам нужно загрузить все библиотеки в таком порядке, чтобы никогда не загружать A до B.

Или, например, у вас есть список зависимых дел - “чтобы сделать А, надо сначала сделать B”, и вам нужно понять, в каком порядке делать все дела.

Во-первых, сразу заметим, что граф с циклом топологически отсортировать не получится - как ни располагай цикл в массиве, все время идти вправо по ребрам цикла не получится, потому что в итоге должен оказаться в самой левой вершине цикла.

Во-вторых, верно обратное! Если цикла нет, то его обязательно можно топологически отсортировать. Попытаемся придумать как, заодно придумаем алгоритм.

Заметим, что вершину, из которой не ведет ни одно ребро, можно всегда поставить последней. И такая вершина всегда есть в графе без циклов (если всегда есть внешнее ребро, то есть цикл). Из этого сразу следует доказательство: просто будем класть в массив вершину, из которой ничего не ведет и убирать ее из графа. Массив потом надо будет развернуть.

Алгоритм же сразу получается, если внимательно посмотреть на время выхода вершин. Вершина, из которой мы вышли в DFS-е первой - как раз та, из которой ничего не выходит. Ведь если из нее есть ребро, то только в уже посещенную, но мы не могли выйти из нее, ведь мы берем самую первую из которой мы вышли. Значит, это одна из серых вершин, в котороые мы вошли, и не вышли, и это цикл.

Из этого следует, что достаточно просто брать вершины в порядке выхода из DFS, то есть в конце DFS, например, просто класть эту вершину в конец массива с ответом. Ну и этот массив надо удет перевернуть, чтобы все ребра шли вправо, а не влево.

Компоненты сильной связности

Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? Ведь в них тоже хочется найти какую-то структуру.

Для этого обычно вводят такое понятие как “сильная связность”. В ориентированных графах две вершины связаны сильно, если существует путь из одной в другую и наоборот. Проще говоря, они обе лежат на каком-то цикле.

Понятно, что такое отношение транзитивно: если А и B сильно связны, и B и C сильно связны, то A и C тоже сильно связны. Поэтому все вершины распадаются на такие компоненты сильной связности - такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильно связности нет.

Самый простой пример сильно-связной компоненты - это цикл. Но это может быть и полный граф, и любое сложное пересечение нескольких циклов.

Часто рассматривают граф самих компонент сильной связности. На катинке выше их шесть, и между ними остаются ребра из изначально графа. Очевидно, что такой граф уже удет ациклических: иначе компоненты на цикле нужно было бы объединить в одну.

Конденсация графа

Задача о конденсации графа звучит так:

Дан ориентированный граф $G$, множество вершин которого $V$ и множество рёбер — $E$. Конденсацией назовем сжатие каждой компоненты сильной связности в одну вершину. Каждой вершине графа конденсации соответствует компонента сильной связности графа $G$, а ориентированное ребро между двумя вершинами $C_i$ и $C_j$ графа конденсации проводится, если найдётся пара вершин $u\in C_i,v\in C_j$, между которыми существовало ребро в исходном графе, т.е. $(u,v)\in E$.

Необходимо найти, какие вершины лежат в каждой компоненте сильной связности и построить граф конденсации.

Теорема. Запустим DFS. Пусть $C$ и $C^{\prime }$ — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро $(C,C^{\prime })$. Тогда $\underset{c\in C}{max}(\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}[c])>\underset{c^{\prime }\in C^{\prime }}{max}(\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}[c^{\prime }])$.

При доказательстве возникают два принципиально различных случая в зависимости от того, в какую из компонент первой зайдёт обход в глубину$:

Первой была достигнута компонента $C$. Это означает, что в какой-то момент времени обход в глубину заходит в некоторую вершину $v$ компоненты $C$, при этом все остальные вершины компонент $C$ и $C^{\prime }$ ещё не посещены. Но, т.к. по условию в графе конденсаций есть ребро $(C,C^{\prime })$, то из вершины $v$ будет достижима не только вся компонента $C$, но и вся компонента $C^{\prime }$. Это означает, что при запуске из вершины $v$ обход в глубину пройдёт по всем вершинам компонент $C$ и $C^{\prime }$, а, значит, они станут потомками по отношению к $v$ в дереве обхода в глубину, т.е. для любой вершины $u\in C\cup C^{\prime },u\ne v$ будет выполнено $\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}[v]>\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}[u]$, ч.т.д.

Обратный случай рассматривается проще, из $C^{\prime }$ нельзя добраться до $C$, а следовательно доказано.

Из этого и следует первая часть решения - давайте отсортируем вершины по убыванию времени выхода (будто топсорт, но на циклическом графе). Рассмотрим компоненту сильной связности первой вершины, назовем ее $C^{\prime }$. В эту компоненту точно нет никаких рёбер из других компонент (иначе $\underset{c\in C}{max}(\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}[c])>\underset{c^{\prime }\in C^{\prime }}{max}(\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}[c^{\prime }])$, а первая вершина - это вообще-то максимум времени выхода). Поэтому если мы развернем все ребра, то из этой вершины все еще будет достижима своя компонента сильной связности $C^{\prime }$, и больше точно ничего - если раньше не было ребер из других компонент, то после разворота ребер не стало ребер в другие компоненты.

Так что второй шаг такой - разворачиваем ребра, запускаем DFS в таком порядке, ищем компоненты связности как в обычном графе. Попутно можно строить и граф конденсации.

vector<int> g[N], gr[N];
bool used[N];
vector<int> order, component;
 
void dfs1(int v) {
    used[v] = true;
    for (int i = 0; i < g[v].size(); i++) {
        if (!used[g[v][i]]) {
            dfs1(g[v][i]);
        }
    }
    order.push_back (v);
}
 
void dfs2(int v) {
    used[v] = true;
    component.push_back(v);
    for (int i = 0; i < gr[v].size(); i++) {
        if (!used[gr[v][i]]) {
            dfs2(gr[v][i]);
        }
    }
}
 
int main() {
    for (;;) {
        g[a].push_back(b);
        gr[b].push_back(a);
    }
    for (int i = 0; i < n; i++){
        if (!used[i]) {
            dfs1(i);
        }
    }
    for (int i = 0; i < n; i++) {
        used[i] = 0;
    }
    reverse(order.begin(), order.end());
    for (int i = 0; i < n; i++) {
        int v = order[i];
        if (!used[v]) {
            dfs2 (v);
        }
    }
}

Еще раз вкратце:

1. Сортируем вершины в порядке убывания времени выхода.

2. Проходимся по массиву вершин в том порядке на равернутом графе и запускаем на нем DFS, выделяя компоненты сильной связности.

2-SAT

Вспомним, что такое конъюнкция (логическое И, обозначается знаком * или $\vee$ или &.) и дизъюнкция (логическое ИЛИ, обозначается знаком + или $\wedge$ или |), конъюкция возвращает 1 тогда и только тогда, когда обе переменные - 1, а дизъюнкция, возвращает 0, когда обе - 0.

Давайте теперь возьмем конъюнкцию дизъюнктов, а именно И от ИЛИ от переменных (или НЕ переменных). Например, такое выражение:

(a | b) & (!c | d) & (!a | !b) // (А ИЛИ B) И (НЕ C ИЛИ D) И (НЕ A ИЛИ НЕ B)

Задача SAT заключается в том, чтобы найти такие значения переменных, при которых это выражение становится истинным, ии сказать, что таких нет. Заметьте, что у нас в каждой скобке в этом примере ровно две переменные, в таком случае задача называется 2-SAT, и именно ее мы и хотим решить. Для примера выше решением является $a=1,b=0,c=0,d=1$ (убедитесь, что все скобки стали True).

Причем тут графы? А вот часто в разных математических задачах надо внезапно ввести граф и он тут же помогает решить задачу.

Приведем сначала выоажение к другому виду - импликативному. Заметим, что выражение вида a | b эквивалентно $!a\to b$ или$!b\to a$.

Построим граф импликаций: для каждой переменной в графе будет по две вершины, обозначим их через $x_i$ и $!x_i$. Рёбра в графе будут соответствовать импликациям.

Теперь заметим, что если для какой-то переменной $x_i$ выполняется, что из $x_i$ достижимо $!x_i$, а из $!x_i$ достижимо $x_i$, то задача решения не имеет. Действительно, какое бы значение для переменной $x_i$ мы бы ни выбрали, мы всегда придём к противоречию - что должно быть выбрано и обратное ему значение. Оказывается, что это условие является не только достаточным, но и необходимым (доказательством этого факта будет описанный ниже алгоритм). Переформулируем данный критерий в терминах теории графов. Напомним, что если из одной вершины достижима вторая и наоборот, то эти две вершины находятся в одной компоненте сильной связности. Тогда мы можем сформулировать критерий существования решения следующим образом:

Для того, чтобы данная задача 2-SAT имела решение, необходимо и достаточно, чтобы для любой переменной $x_i$ вершины $x_i$ и $!x_i$ находились в разных компонентах сильной связности графа импликаций.

Пусть решение существует и нам надо его найти.

Заметим, что, несмотря на то, что решение существует, для некоторых переменных может выполняться, что из $x$ достижимо $!x$ или из $!x$ достижимо $x$. В таком случае выбор одного из значений переменной $x$ будет приводить к противоречию, в то время как выбор другого - не будет. Научимся выбирать из двух значений то, которое не приводит к возникновению противоречий. Сразу заметим, что, выбрав какое-либо значение, мы должны запустить из него обход в глубину/ширину и пометить все значения, которые следуют из него, т.е. достижимы в графе импликаций. Соответственно, для уже помеченных вершин никакого выбора между $x$ и $!x$ делать не нужно, для них значение уже выбрано и зафиксировано. Нижеописанное правило применяется только к непомеченным ещё вершинам.

Утверждается следующее. Пусть $\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[V]$ обозначает номер компоненты сильной связности, которой принадлежит вершина $V$, причём номера упорядочены в порядке топологической сортировки компонент сильной связности в графе компонентов (т.е. более ранним в порядке топологической сортировки соответствуют большие номера: если есть путь из $v$ в $w$, то $\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[v]\le \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[w]$). Тогда, если $\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[x]<\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[!x]$, то выбираем значение !x, иначе выбираем x.

Докажем, что при таком выборе значений мы не придём к противоречию. Пусть, для определённости, выбрана вершина $x$ (случай, когда выбрана вершина $!x$, доказывается также).

Во-первых, докажем, что из $x$ не достижимо $!x$. Действительно, так как номер компоненты сильной связности $\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[x]$ больше номера компоненты $\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}[!x]$ , то это означает, что компонента связности, содержащая $x$, расположена левее компоненты связности, содержащей $!x$, и из первой никак не может быть достижима последняя.

Во-вторых, докажем, что из любой вершины $y$, достижимой из $x$ недостижима $!y$. Докажем это от противного. Пусть из $x$ достижимо $y$, а из $y$ достижимо $!y$. Так как из $x$ достижимо $y$, то, по свойству графа импликаций, из $!y$ будет достижимо $!x$. Но, по предположению, из $y$ достижимо $!y$. Тогда мы получаем, что из $x$ достижимо $!x$, что противоречит условию, что и требовалось доказать.

Итак, мы построили алгоритм, который находит искомые значения переменных в предположении, что для любой переменной $x$ вершины $x$ и $!x$ находятся в разных компонентах сильной связности. Выше показали корректность этого алгоритма. Следовательно, мы одновременно доказали указанный выше критерий существования решения.

Проверка на двудольность

Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.

Пусть первая вершина графа принадлежит первой доли, тогда все вершины, для которых есть ребро в первую, должны принадлежить второй и так далее, но тогда заметим, что если в какой-то момент мы хотем покрасить уже покращенную вершину не в ее цвет, то граф не двудольный, проверить это можно например с помощью дфса : запустим дфс от каждой еще не посешенной вершины.

int n;
vector<int> g[N];

vector<bool> part(n, -1);
void dfs(int u, int color) {
    if (part[u] != color && part[u] != -1) {
        cout << "NO";
        exit(0);
    }
    if (part[u] == color) {
        return;
    }
    for (int i = 0; i < g.size(); i++) {
        dfs(g[u][i], 1 - color);
    }
}