Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.FileInputStream
- import java.nio.file.Files
- import java.nio.file.Paths
- import java.util.*
- import kotlin.collections.ArrayList
- class Task {
- private val n: Int
- private val m: Int
- private val graph: MutableList<MutableList<Int>>
- private val used: MutableList<Int>
- private val ans: MutableList<Int>
- constructor() {
- val scan: Scanner = Scanner(FileInputStream("cycle.in"))
- n = scan.nextInt()
- m = scan.nextInt()
- graph = ArrayList()
- used = ArrayList()
- ans = ArrayList()
- for (i in 0 until n) {
- graph.add(ArrayList())
- used.add(0)
- }
- for (i in 0 until m) {
- val from = scan.nextInt()
- val to = scan.nextInt()
- graph[from - 1].add(to - 1)
- }
- }
- fun dfs(vert: Int): Boolean {
- used[vert] = 1
- ans.add(vert)
- for (a in graph[vert]) {
- if (used[a] == 0) {
- if (dfs(a)) return true
- } else {
- if (used[a] == 1) {
- ans.add(a)
- return true
- }
- }
- }
- ans.removeAt(ans.size - 1)
- used[vert] = 2
- return false
- }
- fun findCycle() {
- val bf = Files.newBufferedWriter(Paths.get("cycle.out"))
- for (i in 0 until n) {
- if (used[i] == 0) {
- if (dfs(i)) {
- bf.write("YES\n")
- var counter = 2
- var cur : Int = ans[ans.size -counter]
- while (cur != ans.last()){
- bf.write((cur + 1).toString() + " ")
- counter++
- cur = ans[ans.size - counter]
- }
- bf.write((cur + 1).toString())
- bf.close()
- return
- }
- }
- }
- bf.write("NO")
- bf.close()
- }
- }
- fun main() {
- val task = Task()
- task.findCycle()
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement