Untitled
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() }