无向图环检测与环还原代码问题排查

任务描述 #

给定一个无向图，判断其是否存在环，若存在则输出该环。

输入数据 #

• 第一行输入顶点数n（1≤n≤500）
• 接下来n行是图的邻接矩阵

输出要求 #

• 若无环，输出NO
• 若有环：
  1. 第一行输出YES
  2. 第二行输出环的顶点数k
  3. 第三行输出k个不同的顶点编号（遍历顺序任意，可从环中任意顶点开始）

示例 #

示例1 #

输入：

3
0 1 1
1 0 1
1 1 0

输出：

YES
3
3 2 1

示例2 #

输入：

4
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0

输出：

NO

我使用DFS结合visited数组进行环检测，通过parent数组还原环，但提交至Yandex的《cycle-search》题目时未通过全部测试用例。以下是我的Kotlin代码，请帮忙排查问题：

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

class Solution {
    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
    }
}

fun main() {
    val solution = Solution()
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine()!!.toInt()
    val graph = Array(n) { IntArray(n) }
    for (i in 0 until n) {
        graph[i] = reader.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    }

    val cycle = solution.findCycle(n, graph)
    if (cycle != null) {
        writer.write("YES\n")
        writer.write("${cycle.size}\n")
        writer.write("${cycle.joinToString(" ")}\n")
    } else {
        writer.write("NO\n")
    }

    reader.close()
    writer.close()
}

内容的提问来源于stack exchange，提问作者Aleksandr T