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

• Для каждой вершины v будем подсчитывать время входа tIn[v] и величину tUp[v] — минимальное tIn для некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
• Ребро (v — u) является мостом, если из поддерева вершины v в дереве обхода в глубину нет обратных рёбер в вершину u или её предков (tUp[v] > tIn[u]).

vector<int> g[V_CNT];
bool u[V_CNT];
int tIn[V_CNT], tUp[V_CNT], timer; 

void dfs(int v, int parent = -1) {
    u[v] = 1;
    tUp[v] = tIn[v] = timer++;
    for (int i = 0; i < g[v].size(); i++) {
        if (!u[g[v][i]]) {
            dfs(g[v][i], v);
            tUp[v] = min(tUp[v], tUp[g[v][i]]);
            if (tUp[g[v][i]] > tIn[v])
                /* (v, g[v][i]) - мост */;
        } else if (g[v][i] != parent)
            tUp[v] = min(tUp[v], tIn[g[v][i]]);
    }     
}

for (int i = 0; i < V_CNT; i++)
    u[i] = tIn[i] = tUp[i] = 0;
timer = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs(i);

Ссылки на задачи

• Codeforces #100070.E — Неизбежность

Ссылки

• e-maxx.ru — Поиск мостов
• neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска мостов
• neerc.ifmo.ru/wiki — Построение компонент реберной двусвязности
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
• Лахно А. П. Поиск в глубину и его применение
• VisuAlgo — Graph Traversal
• CodeLibrary — Biconnected components, bridges and cut points
• Algos — Algorithm for finding all bridges in the graph