Мосты. Компоненты рёберной двусвязности: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 2: Строка 2:
* Ребро (<tt>v</tt> &mdash; <tt>to</tt>) является мостом, если из поддерева вершины <tt>to</tt> в дереве обхода в глубину нет обратных рёбер в вершину <tt>v</tt> или её предков (<tt>upDepth[to] > depth[v]</tt>).
* Ребро (<tt>v</tt> &mdash; <tt>to</tt>) является мостом, если из поддерева вершины <tt>to</tt> в дереве обхода в глубину нет обратных рёбер в вершину <tt>v</tt> или её предков (<tt>upDepth[to] > depth[v]</tt>).


  vector<vector<int>> graph(vertexCount);
  struct Graph {
vector<bool> visited(vertexCount);
    vector<vector<int>> g;
vector<int> depth(vertexCount); // глубина вершины в дереве обхода
    vector<int> visited, depth, upDepth;
vector<int> upDepth(vertexCount); // насколько высоко можно добраться из поддерева вершины, пройдя 1 раз по обратному ребру
    vector<pair<int, int>> bridges;
   
   
void dfs(int v, int parent) {
    void dfs(int v, int p) {
    visited[v] = 1;
        visited[v] = 1;
    depth[v] = (parent == -1 ? 0 : depth[parent] + 1);
        depth[v] = (p == -1 ? 0 : depth[p] + 1);
    upDepth[v] = depth[v];
        upDepth[v] = depth[v];
   
   
    for (int to : graph[v]) {
        for (int to : g[v]) {
        if (to == parent) {
            if (to == p) {
            continue;
                continue;
        } else if (!visited[to]) {
            } else if (!visited[to]) {
            dfs(to, v);
                dfs(to, v);
            upDepth[v] = min(upDepth[v], upDepth[to]);
                upDepth[v] = min(upDepth[v], upDepth[to]);
            if (upDepth[to] > depth[v])
                if (upDepth[to] > depth[v])
                /* (v, to) - мост */;
                    bridges.push_back({ v, to });
        } else {
            } else {
            upDepth[v] = min(upDepth[v], depth[to]);
                upDepth[v] = min(upDepth[v], depth[to]);
            }
         }
         }
     }   
     }
}
   
   
  for (int v = 0; v < vertexCount; v++)
    Graph(int vertexCount) {
    if (!visited[v])
        g.resize(vertexCount);
        dfs(v, -1);
        visited.resize(vertexCount);
        depth.resize(vertexCount);
        upDepth.resize(vertexCount);
    }
    void addEdge(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
   
    vector<pair<int, int>> getBridges() {
        for (int v = 0; v < g.size(); v++)
            if (!visited[v])
                dfs(v, -1);
        return bridges;
    }
};


== Ссылки ==
== Ссылки ==

Версия от 14:40, 4 июня 2021

  • Для каждой вершины v будем подсчитывать глубину depth[v] и величину upDepth[v] — минимальную глубину некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
  • Ребро (vto) является мостом, если из поддерева вершины to в дереве обхода в глубину нет обратных рёбер в вершину v или её предков (upDepth[to] > depth[v]).
struct Graph {
    vector<vector<int>> g;
    vector<int> visited, depth, upDepth;
    vector<pair<int, int>> bridges;

    void dfs(int v, int p) {
        visited[v] = 1;
        depth[v] = (p == -1 ? 0 : depth[p] + 1);
        upDepth[v] = depth[v];

        for (int to : g[v]) {
            if (to == p) {
                continue;
            } else if (!visited[to]) {
                dfs(to, v);
                upDepth[v] = min(upDepth[v], upDepth[to]);
                if (upDepth[to] > depth[v])
                    bridges.push_back({ v, to });
            } else {
                upDepth[v] = min(upDepth[v], depth[to]);
            }
        }
    }

    Graph(int vertexCount) {
        g.resize(vertexCount);
        visited.resize(vertexCount);
        depth.resize(vertexCount);
        upDepth.resize(vertexCount);
    }

    void addEdge(int a, int b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<pair<int, int>> getBridges() {
        for (int v = 0; v < g.size(); v++)
            if (!visited[v])
                dfs(v, -1);
        return bridges;
    }
};

Ссылки

Теория:

Демонстрация:

Код:

Задачи: