Обнаружение цикла в неориентированном графе
Графы
Средняя
Неориентированный граф задан числом вершин n и списком рёбер edges. Верните true, если в графе есть цикл.
Классический способ - система непересекающихся множеств (DSU): если при обработке ребра его концы уже в одном множестве, ребро замыкает цикл.
Сигнатура функции
has_cycle(n: int, edges: list[list[int]]) -> bool
Примеры
| Вход | Ожидаемый результат |
|---|
| [4, [[0, 1], [1, 2], [2, 3]]] | false |
| [4, [[0, 1], [1, 2], [2, 3], [3, 0]]] | true |
1решили
1пытались
100%успешность
Войдите, чтобы решить →