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