Untitled
unknown
kotlin
2 years ago
1.9 kB
14
Indexable
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()
}Editor is loading...