bridges.md

Мосты и точки сочленения

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

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

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

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

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

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++;
}

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

Мосты

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

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

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

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

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

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

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

2. $dp_{i} = min(tin_{i}, dp_{i})$

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

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

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

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]) {
            //ребро - мост
        }
    }
}

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

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

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

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 - точка сочленения;
    }
}