Точки сочленения
Графы
Экстремальная
Дан неориентированный граф: n вершин, список рёбер edges. Точка сочленения - вершина, при удалении которой (вместе со всеми её рёбрами) граф распадается на больше компонент связности.
Верните отсортированный список всех точек сочленения (алгоритм Тарьяна; для корня дерева обхода условие особое - он точка сочленения, если у него больше одного потомка в дереве обхода).
Сигнатура функции
find_articulation_points(n: int, edges: list[list[int]]) -> list[int]
Примеры
| Вход | Ожидаемый результат |
|---|
| [5, [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]]] | [1, 3] |
| [2, [[0, 1]]] | [] |
1решили
1пытались
100%успешность
Войдите, чтобы решить →