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

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

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

Код: 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)