Untitled

mail@pastecode.io avatar
unknown
kotlin
a year ago
1.9 kB
7
Indexable
Never
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()
}