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

Как их находить? Производится запуск дфс-а и для каждого поддерева определяется минимальная высота вершины, в которую можно попасть из данного поддерева одним непрямым ребром. Если нельзя подняться выше, чем корень поддерева (u) из поддерева вершины v (v — сын u), то u -> v — мост.

Код: C++

map<ll, map <ll, bool>> is_most; vector<vector>g; vectorh; vectordp; vectorvisited; void dfs(ll u, ll p) { if (p == -1) h[u] = 0; else h[u] = h[p] + 1; dp[u] = h[u]; visited[u] = true; for (auto& v : g[u]) { if (v == p) { continue; } if (visited[v]) { dp[u] = min(dp[u], h[v]); } else { dfs(v, u); dp[u] = min(dp[u], dp[v]); if (dp[v] > h[u]) { is_most[v][u] = true; is_most[u][v] = true; } } } }

Где: is_most — is_most[v][u] значит u -> v — мост g — списки смежности h — высота каждой вершины dp — минимальная высота подъема из поддерева

Асимптотика — O((n + m)*logm)

P.S. Если какие-то ребра являются кратными, то они не могут быть мостами