Напоминание

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

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

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

Давайте назовем массивы $\space{\rm tin}$ и ${\rm tout}$, где ${\rm tin}$ - время входа, а $\space{\rm tout}$ - время выхода из вершины.

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

In [0]:
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++;
}

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

Мосты

Пусть дан связный неориентированный граф. Мост - ребро, при удалении которой граф становится несвязным.

Первым делом введем новые виды ребер :

1) Ребра самого ДФС (tree edge или ребро дерева).

2) Ребра не посещенные в ДФС (back edge или. обратное ребро).

Пусть есть ребро $u \rightarrow v$, в каком случае оно является мостом, понятно, что обратное ребро не может быть мостом, потому что мы уже посещали обе вершины и следовательно есть путь по ребрам самого ДФС. Теперь разберемся с ребрами ДФС. Они являются мостом, только если нет пути по обратным ребрам в какого-то из предков $v$. Так как иначе мы можем удалить это ребро, но при этом останется путь по обратным ребрам.

Давайте докажем, что если путь до предка существует, то существует и путь, такой, что нам достаточно пройти по одному обратному ребру. Пусть такого пути не существует, но при этом есть какой-то путь из $n$ обратных ребер, тогда давайте посмотрим куда могут вести эти ребра, они могут вести либо в поддерево вершины $u$, либо в нее саму, либо в наддерево, в случае поддерева или самой вершины мы можем их убрать, так как есть путь по ребрам ДФС, в случае наддерева же нам достаточно сохранить только одно ребро в наддерево.

Тогда давайте введем $dp_{i}$ - минимальный $\space{\rm tin}$ такой вершины, до которой мы можем добраться за какое-то количество ребер ДФС и одно обратное. Как его пересчитывать. Очень просто : у нас есть три возможных значения динамики.

1) $dp_{i} = min(tin_{i}, dp_{i})$

2) $dp_{i} = min(dp_{i}, dp_{son})$, где $son$ - сын $i$-й вершины

3) $dp_{i} = min(dp_{i}, tin_{back})$, где $back$ - вершина, для которой есть обратное ребро из $i$-й вершины.

Научимся понимать, какое ребро - ребро ДФС, а какое обратное. Если ребро ведет в уже использованную вершины, то это обратное ребро, иначе ребро ДФС.

In [0]:
int timer, tin[MAXN], dp[MAXN];
 
void dfs(int u, int p) {
    used[u] = true;
    tin[u] = dp[v] = timer++;
    for (auto to : g[v]) {
        if (to == p) {
            continue;
        }
        if (used[to]) {
            dp[u] = min(dp[u], tin[to]);
        }
        else {
            dfs(to, u);
            dp[u] = min(dp[u], dp[to]);
        }
        if (dp[to] > tin[u]) {
            //ребро - мост
        }
    }
}

Точки сочленения

Точка сочленения - вершина, при удалении которой граф становится несвязным.

Первое, что надо заметить, что мост и точка сочленения очень похожи, а что если они и ищутся одинаково. Давайте подумаем, что такое точка сочленения в рамках обратных ребер, это вершина у которой можно добраться до предка используя обратные и ребра ДФС вниз. Но тогда как изменится нахождение точек сочленения, единственное отличие, что у мостов надо было чтобы у предка было время входа строго больше, сейчас же нам достаточно и нестрогого неравенства, так как если из вершины можно добраться до нее самой, то она все равно точка сочленения. Также вылезает один крайний случай, а именно корень, так как в корень мы всегда войдем раньше других вершин, но тут решение очень простое, давайте посмотрим, сколько несвязных поддеревьев у корня.

In [0]:
int timer, tin[MAXN], dp[MAXN];
 
void dfs(int u, int p = -1) {
    used[u] = 1;
    tin[u] = dp[u] = timer++;
    int children = 0;
    for (auto to : g[u]) {
        if (to == p)  {
            continue;
        }
        if (used[to]) {
            dp[u] = min(dp[u], tin[to]);
        }
        else {
            dfs(to, u);
            dp[u] = min(dp[u], dp[to]);
        }
        if (dp[to] >= tin[u] && p != -1) {
            //v - точка сочленения;
        }
        ++children;
    }
    if (p == -1 && children > 1) {
        //u - точка сочленения;
    }
}

Эйлеров путь и цикл

Эйлеров путь - это путь в графе, проходящий через все его рёбра. Эйлеров цикл - это эйлеров путь, являющийся циклом.

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

Чтобы проверить, существует ли эйлеров путь, нужно воспользоваться следующей теоремой.

Пусть дан неориентированный связный цикл. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями равно двум (или нулю, в случае существования эйлерова цикла).

Кстати, аналогичная теорема есть и для ориентированного графа (можете сами попытаться сформулировать).

Доказать это можно например через лемму о рукопожатиях.

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


In [0]:
void findeulerpath(int v){
    stack<pair<int, int> >s;
    s.push({v, -1});
    while (!s.empty()) {
        v = s.top().first;
        int x = s.top().second;
        for (int i = 0; i < g[v].size(); i++){
            pair<int, int> e = g[v][i];
            if(!u[e.second]){
                u[e.second]=1;
                s.push(e);
                break;
            }
        }
        if (v == s.top().first) {
            if (~x) {
                p.push_back(x);
            }
            s.pop();
        }
    }
}