Всем привет Есть достаточно базовая задача: Дан неориентированный граф. Требуется определить, есть

ли в нем цикл, и, если есть, вывести его.

Входные данные подаются в виде матрицы смежности. Надо определить, есть ли цикл и восстановить его. Кажется что задача вполне себе базовая, нужно запоминать массив родителей чтобы успешно восстановить цикл. У меня получился такой код: https://pastecode.io/s/5mbbjioe
fun findCycle(n: Int, graph: Array<IntArray>): List<Int>? {
val visited = BooleanArray(n)
val parent = IntArray(n) { -1 }

fun dfs(v: Int): List<Int>? {
visited[v] = true
for (u in 0 until n) {
if (graph[v][u] == 1) {
if (!visited[u]) {
parent[u] = v
val cycle = dfs(u)
if (cycle != null) return cycle
} else if (parent[v] != u) {
val cycle = mutableListOf<Int>()
var cur = v
while (cur != -1) {
cycle.add(cur + 1)
cur = parent[cur]
}
return cycle.reversed()
}
}
}
return null
}

for (v in 0 until n) {
if (!visited[v]) {
val cycle = dfs(v)
if (cycle != null) return cycle
}
}

return null
}


Но у меня решение валится на одном из тестов, не могу понять где же сделал ошибку, не подскажите где она может быть?

что за язык прог.е?

Типа Rust

котлин

L22, while (cur != -1) {, кмк, условие неправильное; допустим, мы зашли в компоненту графа, хвостик не образующий цикла, и цикл. Тут мы выведем цикл и хвостик, а надо только до начала цикла.

конечно, надо поработать над стилем, читать очень неудобно (в частности visit стоит проверять внутри функции dfs) > Дан неориентированный граф. Требуется определить, есть ли в нем цикл то есть определить, что одна из компонент связности имеет |E| >= |V| ? > while (cur != -1) while (cur != u) мб?

Хм, похоже на правду, т.е получается вот так примерно fun processCycle(v: Int, n: Int) { var curr = v while (parent[curr] != n) { cycle.add(curr) curr = parent[curr] } }

Про стиль не совсем понял коммент, я написал этот код по шаблону на самом деле с одной лекции

Не знаю что вы делаете, но пмсм если цель обнаружить цикл, то есть известная тема с двумя указателями - один переходит один узел за раз, другой два узла, соотвественно если цикла нет от стартового узла, то более шустрый указатель выйдет к листу, если цикл есть, то в какой-то момент попадя в цикл один указатель догонит второй за меньше чем 2N+K, где N - длина цикла, K длина цепочки вне цикла, последующее восстановление возможно просто запоминанием точки встречи и полным проходом по циклу. Массив родителей я бы не хранил, если конечно у вас не какой-то сверхтривиальный и миниатюрный граф, в котором цепочка вне цикла будет очень короткой, единственное что возможно был бы смысл дополнительно вести стек пар "узел, узел_перехода", дабы по нему принимать решения о посещениях узлов с несколькими исходящими рёбрами.

Цель не просто обнаружить цикл, а восстановить его. Ну ив графах все-таки обычно используют DFS с "цветами", где: 0 - непосещенная вершина (white) 1 - вершина уже посещалась, но не закончена процесситься (grey) 2 - вершина закончена процессится (black)

Кажется, что вы какую-то другую задачу имеете в виду