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

Как их находить? Производится запуск дфс-а и для каждого поддерева определяется минимальная высота вершины, в которую можно попасть из данного поддерева одним непрямым ребром. Если нельзя подняться выше, чем корень поддерева (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. Если какие-то ребра являются кратными, то они не могут быть мостами

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

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

Нюанс — для корня дерева нужно делать отдельную проверку на кол-во детей (если ребенок один, то корень не является точкой сочленения)

Код: C++ vector<vector>g; vectoris_ts; 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; ll ch = 0; for (auto& v : g[u]) { if (v == p) { continue; } if (visited[v]) { dp[u] = min(dp[u], h[v]); } else { dfs(v, u); ch++; dp[u] = min(dp[u], dp[v]); if (p != -1 and dp[v] >= h[u]) { is_ts[u] = true; } } } if (p == -1 and ch > 1) is_ts[u] = true; }

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

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

Что это такое?

Паросочетание — набор попарно несмежных рёбер графа.

Максимальное паросочетание — паросочетание, мощность которого максимальна среди всех возможных паросочетаний в данном графе.

Мощность паросочетания — количество рёбер в нём.

Как их находить? Существует алгоритм Куна, который основывается на поиске увеличивающихся цепей, пока ищется, и проведении чередования в них.

Код: C++ vector<vector>g; vectormatch; vectorused; bool kun(ll v) { if (used[v])return false; used[v] = true; for (auto& u : g[v]) { if (match[u] == -1) { match[u] = v; return true; } } for (auto& u : g[v]) { if (kun(match[u])) { match[u] = v; return true; } } return false; }

Где: g — списки смежности match[i] — вершина из левой доли, которая сопоставлена вершине i из правой доли used — была ли посещена вершина

Для нахождения максимального паросочетания необходимо произвести запуск данного алгоритма от каждой вершины левой доли (каждый раз надо чистить массив used).

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

P.S. Для ускорения я используется два раздельных цикла в самом алгоритме, т.к. сначала проверяются все вершины и ищется "несматченная" вершина, а это дает неплохое ускорение (только в частных случаях)