Код Senior Графы: BFS и DFS обновлено
Цикл в ориентированном графе
Условие
Есть ли цикл в ориентированном графе, заданном списком смежности?
Примеры
hasCycle({"a":["b"],"b":["c"],"c":["a"]}) // true
hasCycle({"a":["b"],"b":["c"],"c":[]}) // false
hasCycle({"a":["b"],"b":["a"]}) // true
Как подойти
Три цвета: белый (не трогали), серый (в текущем пути рекурсии), чёрный (обработан). Цикл - это ребро в серую вершину. С двумя состояниями ромбовидный граф ошибочно объявляется циклическим. Для неориентированного графа правила другие - там достаточно не считать циклом ребро к родителю.
Подсказки: 2
- Двух состояний «посещён / не посещён» недостаточно.
- Нужно отличать «в текущем пути» от «полностью обработан».
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.