5704. Есть ли цикл

Medium 0 решили
Неориентированный граф без петель. Верните true, если есть цикл: путь длины ≥ 3, который возвращается в уже посещённую вершину не через родителя.
Дерево и набор несвязных деревьев — false. Треугольник в одной компоненте достаточно, даже если остальные вершины висят отдельно.

Примеры:

Вход: n = 3, edges = [[0,1],[1,2],[2,0]]
Выход: true
Объяснение: Треугольник.
Вход: n = 4, edges = [[0,1],[1,2],[2,3]]
Выход: false
Объяснение: Путь без цикла.
Вход: n = 1, edges = []
Выход: false
Объяснение: Одна вершина.

Ограничения:

1 <= n <= 2000

Теги:

Графы

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!