Feb 19 2021 at 01:24

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

Invite pending

Мосты

Определение

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

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

Суть алгоритма

Идея

Мы можем заметить тот факт, что ребро между точками v и u является мостом тогда и только тогда, когда из вершины u и её потомков нельзя вернуться в вершину v или подняться выше нее. Осталось лишь понять, как нам это выяснить.

Алгоритм

Разобьём ребра на ориентированные и будем хранить их в отдельной структуре. Пусть мы будем запоминать номер вершины, в которую направлено ребро, номер данного ребра (номер ребра равен номеру обратного ребра) и ссылку на его обратное ребро.

Заведём граф ссылок на рёбра и заполним его.

Запустим обход графа в глубину (DFS).

Будем для каждой вершины v хранить два значения:

dp[v] - минимально возможная вершина в которую мы можем опуститься из этой вершины в процессе обхода в глубину (по умолчанию текущая глубина)
d[v] - глубина текущей вершины

В процессе обхода:

Если встречаем вершину u, в которой еще не были, то спускаемся в неё и тогда dp[v] = min(dp[v], dp[u]). Тем самым проверяем опустились ли мы из вершины u и её потомков выше v.
Если встречаем вершину v, в которой уже были, то dp[v] = min(dp[v], d[u]). Тем самым проверяем не встретили ли мы вершину выше по обходу графа, чем вершина v.

По завершении обхода вершины v и её потомков:

Если из вершины v нельзя опуститься выше нее самой и мы знаем проверяемое ребро (dp[v] == d[v] && p != nullptr(текущее ребро)), то ребро из этой вершины - есть мост.

Тогда:

p->is_bridge = true - вершина v

p->bck->is_bridge = true - вершина другого конца ребра

Реализация

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

struct Edge{
    ll v,num;
    bool is_bridge;
    Edge* bck;
    Edge(){}
    Edge(ll v, ll num):v(v),num(num){}
};

vector<vector<Edge*>> gr;
vector<ll> dp,d,bridges;
vector<bool> used;

void dfs(ll v, ll depth = 0, Edge* p = nullptr){
    used[v] = true;
    dp[v] = d[v] = depth;
    for(auto u : gr[v]){
        if(!used[u->v]){
            dfs(u->v,depth+1,u);
            dp[v] = min(dp[v],dp[u->v]);
        }
        else if (p && p->num != u->num){
            dp[v] = min(dp[v],d[u->v]);
        }
    }
    if(p != nullptr && dp[v] == d[v]){
        p->is_bridge = true;
        p->bck->is_bridge = true;
        bridges.push_back(p->num+1);
    }
}

int main(){
    fast_cin();
    ll n,m;
    cin >> n >> m;
    gr.resize(n);
    dp.resize(n);
    d.resize(n);
    used.resize(n);
    ll v,u;
    for(ll i = 0;i < m;i++){
        cin >> v >> u;
        v--;
        u--;
        Edge* a = new Edge(u,i);
        Edge* b = new Edge(v,i);
        a->bck = b;
        b->bck = a;
        gr[v].push_back(a);
        gr[u].push_back(b);
    }
    for(ll i = 0;i < n;i++)
        if(!used[i])
            dfs(i);

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

    cout << bridges.size() << endl;
    for(auto i : bridges){
        cout << i << " ";
    }
}

Задачи по теме

https://informatics.mccme.ru/mod/statements/view.php?id=31311#1

https://informatics.mccme.ru/mod/statements/view.php?id=40111&chapterid=389#

https://informatics.mccme.ru/mod/statements/view.php?id=28842#1

https://informatics.mccme.ru/mod/statements/view.php?id=28842&chapterid=3586#1

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

Определение

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

Суть алгоритма

Идея

Мы можем заметить два факта:

Рассмотрим ребро между вершинами v и u. Тогда если из вершины u и ее потомков нельзя попасть в какого-либо предка вершины v и притом вершина v не является корнем дерева, то данная вершина и есть точка сочленения
Если вершина v - корень дерева, то она является точкой сочленения тогда и только тогда, когда эта точка имеет более одного сына в обходе графа в глубину

Алгоритм

Заведем общий счетчик времени входа timer и два массива:

tin[v] - время входа в вершину v
fup[v] - минимально достижимая вершина из вершины v

Запустим обход графа в глубину (DFS).

В процессе обхода:

Если встречаем уже посещенную вершину u, то fup[v] = min(fup[v], tin[u]). Проверяем не спустились ли мы выше v.
Если встречаем не посещенную вершину v, то спускаемся в неё. Затем fup[v] = min(fup[v], fup[u]). Тем самым проверим не спустились ли мы выше v из вершины u и ее потомков. И наконец если из вершины u нельзя спуститься ниже вершины v и вершины v - не корень дерева обхода графа (v fup[u] >= tin[v] && p != -1), то вершина v и есть искомая точка сочленения. Добавляем 1 к количеству сыновей вершины v (children++)

По завершении обхода:

Если вершина v является корнем обхода графа в глубину и имеет более одного сына, то она также является точкой сочленения (p == -1 && children > 1)

Реализация

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
ll timer = 0;
vector<vector<ll>> gr;
vector<ll> tin,fup;
set<ll> points_of_connectebility;
vector<bool> used;

void dfs(ll v,ll p = -1){
    used[v] = true;
    tin[v] = fup[v] = timer++;
    ll children = 0;
    for(auto u : gr[v]){
        if(u == p){
            continue;
        }
        if(used[u]){
            fup[v] = min(fup[v],tin[u]);
        }
        else{
            dfs(u,v);
            fup[v] = min(fup[v],fup[u]);
            if(fup[u] >= tin[v] && p != -1){
                points_of_connectebility.insert(v+1);
            }
            children++;
        }
    }
    if(p == -1 && children > 1){
        points_of_connectebility.insert(v+1);
    }
}

int main() {
    fast_cin();
    ll n, m;
    cin >> n >> m;
    gr.resize(n);
    tin.resize(n);
    fup.resize(n);
    used.resize(n);
    ll v, u;
    for (ll i = 0; i < m; i++) {
        cin >> v >> u;
        v--;
        u--;
        gr[v].push_back(u);
        gr[u].push_back(v);
    }

    for (ll i = 0; i < n; i++)
        if (!used[i])
            dfs(i);

    cout << points_of_connectebility.size() << endl;
    for(auto i : points_of_connectebility){
        cout << i << " ";
    }
}

Задачи по теме

https://informatics.mccme.ru/mod/statements/view3.php?id=40111&chapterid=111690#1

https://informatics.mccme.ru/mod/statements/view.php?id=40111&chapterid=111795#1

https://informatics.mccme.ru/mod/statements/view.php?id=40111&chapterid=3883#1

https://informatics.mccme.ru/mod/statements/view.php?id=40111&chapterid=3586#1

Hubs: