Мосты. Компоненты рёберной двусвязности
Перейти к навигации
Перейти к поиску
- Для каждой вершины v будем подсчитывать глубину depth[v] и величину upDepth[v] — минимальную глубину некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
- Ребро (v — to) является мостом, если из поддерева вершины to в дереве обхода в глубину нет обратных рёбер в вершину v или её предков (upDepth[to] > depth[v]).
struct Graph {
vector<vector<int>> graph;
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 : graph[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) :
graph(vertexCount), visited(vertexCount), depth(vertexCount), upDepth(vertexCount) {}
void addEdge(int a, int b) {
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<pair<int, int>> getBridges() {
for (int v = 0; v < graph.size(); v++)
if (!visited[v])
dfs(v, -1);
return bridges;
}
};
Ссылки
Теория:
Демонстрация:
Код:
Задачи: