kz-maxx

RU KZ
← Главная

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

DFS, tin, low, мосты, articulation points в неориентированном графе

Что такое мост?

Мост — это ребро в неориентированном графе, после удаления которого количество компонент связности увеличивается.

Проще:

если удалить ребро
и граф развалится на большее количество частей
значит это ребро — мост

Пример:

1 -- 2 -- 3
ребро 2--3 является мостом

Что такое точка сочленения?

Точка сочленения — это вершина, после удаления которой количество компонент связности увеличивается.

Проще:

если удалить вершину
и граф развалится на большее количество частей
значит эта вершина — точка сочленения

Пример:

1 -- 2 -- 3
вершина 2 является точкой сочленения

Где используется?

  • проверка надежности сети
  • поиск слабых мест в графе
  • дороги, мосты, маршруты
  • компьютерные сети
  • задачи на связность графа
  • DFS в неориентированном графе

Главная идея

Для поиска мостов и точек сочленения используется DFS. Для каждой вершины храним два значения:

  • tin[v] — время входа в вершину v
  • low[v] — минимальное tin, куда можно добраться из v или из ее поддерева
int tin[N];
int low[N];
int timer;

Что такое tin?

tin[v] — это время, когда DFS впервые зашел в вершину v.

Например:

dfs(1) → tin[1] = 0
dfs(2) → tin[2] = 1
dfs(3) → tin[3] = 2 
tin[v] = timer;
low[v] = timer;
timer++;

Что такое low?

low[v] — это минимальное время входа вершины, в которую можно попасть:

  • из самой вершины v
  • из потомков вершины v
  • через обратное ребро
low помогает понять, есть ли путь из поддерева назад вверх. Если такого пути нет, ребро может быть мостом.

DFS для tin и low

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
        }
    }
}

Здесь:

  • v — текущая вершина
  • p — родитель вершины v в DFS
  • to — сосед вершины v

Условие моста

Ребро v -- to является мостом, если: 

low[to] > tin[v]

Почему?

low[to] > tin[v]
значит из поддерева to нельзя подняться обратно к v или выше
значит ребро v--to единственная связь
значит это мост

Задача 1: найти все мосты

Дан неориентированный граф. Нужно вывести все мосты.

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

3 4
4 5

Ребра 3--4 и 4--5 — мосты.

Полная реализация мостов

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
int tin[N];
int low[N];
int timer = 0;

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                cout << v << ' ' << to << '\n';
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    return 0;
}

Важный момент про кратные ребра

Если между двумя вершинами есть несколько ребер, простой код с to == p может ошибиться.

Чтобы решить это правильно, лучше хранить номер ребра. 

vector<pair<int, int>> g[N];

Где:

  • first — соседняя вершина
  • second — номер ребра

Мосты с номерами ребер

void dfs(int v, int parentEdge) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (auto edge : g[v]) {
        int to = edge.first;
        int id = edge.second;

        if (id == parentEdge) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, id);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                bridges.push_back(id);
            }
        }
    }
}

Полная реализация мостов с id

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<pair<int, int>> g[N];
bool used[N];
int tin[N];
int low[N];
int timer = 0;
vector<int> bridges;

void dfs(int v, int parentEdge) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    for (auto edge : g[v]) {
        int to = edge.first;
        int id = edge.second;

        if (id == parentEdge) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, id);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                bridges.push_back(id);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    vector<pair<int, int>> edges(m + 1);

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        edges[i] = {a, b};

        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    sort(bridges.begin(), bridges.end());

    for (int id : bridges) {
        cout << edges[id].first << ' ' << edges[id].second << '\n';
    }

    return 0;
}

Условие точки сочленения

Для вершины v и ее ребенка to в DFS: 

low[to] >= tin[v]

Если это выполняется, то вершина v может быть точкой сочленения.

low[to] >= tin[v]
значит поддерево to не может подняться выше v
если удалить v, это поддерево отделится

Особый случай: корень DFS

Для корня DFS правило другое.

Корень является точкой сочленения, если у него больше одного ребенка в DFS-дереве. 

if (p == -1 && children > 1) {
    isCut[v] = true;
}
Если у корня только один ребенок, удаление корня не увеличит количество компонент.

Задача 2: найти точки сочленения

Дан неориентированный граф. Нужно вывести все точки сочленения.

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

3 4

Вершины 3 и 4 — точки сочленения.

Полная реализация точек сочленения

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
bool isCut[N];
int tin[N];
int low[N];
int timer = 0;

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    int children = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] >= tin[v] && p != -1) {
                isCut[v] = true;
            }

            children++;
        }
    }

    if (p == -1 && children > 1) {
        isCut[v] = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (isCut[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

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

Можно в одном DFS искать и мосты, и точки сочленения.

Условия:

мост: low[to] > tin[v]
точка сочленения: low[to] >= tin[v]

Разница в знаке:

  • > для моста
  • >= для точки сочленения

Полная реализация вместе

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, m;
vector<int> g[N];
bool used[N];
bool isCut[N];
int tin[N];
int low[N];
int timer = 0;
vector<pair<int, int>> bridges;

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    int children = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                bridges.push_back({v, to});
            }

            if (low[to] >= tin[v] && p != -1) {
                isCut[v] = true;
            }

            children++;
        }
    }

    if (p == -1 && children > 1) {
        isCut[v] = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    cout << "Bridges:\n";

    for (auto e : bridges) {
        cout << e.first << ' ' << e.second << '\n';
    }

    cout << "Cut points:\n";

    for (int i = 1; i <= n; i++) {
        if (isCut[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

Как запомнить условия?

Объект Условие Смысл
Мост low[to] > tin[v] нет пути обратно к v или выше
Точка сочленения low[to] >= tin[v] поддерево не может подняться выше v
Корень DFS children > 1 после удаления корня дети станут разными компонентами

Типичные ошибки

  • Забыть запустить DFS из всех компонент
  • Перепутать условия > и >=
  • Не обработать особый случай корня
  • Использовать простой to == p при кратных ребрах
  • Забыть обновить low[v] после DFS в ребенка
  • Забыть обновить low[v] через обратное ребро

Асимптотика

Что ищем Время Память
Мосты O(n + m) O(n + m)
Точки сочленения O(n + m) O(n + m)
Вместе O(n + m) O(n + m)
DFS проходит каждую вершину и каждое ребро максимум несколько раз, поэтому время работы O(n + m).

Короткий шаблон

void dfs(int v, int p) {
    used[v] = true;
    tin[v] = low[v] = timer++;

    int children = 0;

    for (int to : g[v]) {
        if (to == p) {
            continue;
        }

        if (used[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);

            if (low[to] > tin[v]) {
                cout << "bridge " << v << ' ' << to << '\n';
            }

            if (low[to] >= tin[v] && p != -1) {
                isCut[v] = true;
            }

            children++;
        }
    }

    if (p == -1 && children > 1) {
        isCut[v] = true;
    }
}