Advertisement
Guest User

Untitled

a guest
Feb 25th, 2020
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 2.07 KB | None | 0 0
  1. import java.io.FileInputStream
  2. import java.nio.file.Files
  3. import java.nio.file.Paths
  4. import java.util.*
  5. import kotlin.collections.ArrayList
  6.  
  7. class Task {
  8.     private val n: Int
  9.     private val m: Int
  10.     private val graph: MutableList<MutableList<Int>>
  11.     private val used: MutableList<Int>
  12.     private val ans: MutableList<Int>
  13.  
  14.     constructor() {
  15.         val scan: Scanner = Scanner(FileInputStream("cycle.in"))
  16.         n = scan.nextInt()
  17.         m = scan.nextInt()
  18.         graph = ArrayList()
  19.         used = ArrayList()
  20.         ans = ArrayList()
  21.         for (i in 0 until n) {
  22.             graph.add(ArrayList())
  23.             used.add(0)
  24.         }
  25.         for (i in 0 until m) {
  26.             val from = scan.nextInt()
  27.             val to = scan.nextInt()
  28.             graph[from - 1].add(to - 1)
  29.         }
  30.     }
  31.  
  32.     fun dfs(vert: Int): Boolean {
  33.         used[vert] = 1
  34.         ans.add(vert)
  35.         for (a in graph[vert]) {
  36.             if (used[a] == 0) {
  37.                 if (dfs(a)) return true
  38.             } else {
  39.                 if (used[a] == 1) {
  40.                     ans.add(a)
  41.                     return true
  42.                 }
  43.             }
  44.         }
  45.         ans.removeAt(ans.size - 1)
  46.         used[vert] = 2
  47.         return false
  48.     }
  49.  
  50.     fun findCycle() {
  51.         val bf = Files.newBufferedWriter(Paths.get("cycle.out"))
  52.         for (i in 0 until n) {
  53.             if (used[i] == 0) {
  54.                 if (dfs(i)) {
  55.                     bf.write("YES\n")
  56.                     var counter = 2
  57.                     var cur : Int = ans[ans.size -counter]
  58.                     while (cur != ans.last()){
  59.                         bf.write((cur + 1).toString() + " ")
  60.                         counter++
  61.                         cur = ans[ans.size - counter]
  62.                     }
  63.                     bf.write((cur + 1).toString())
  64.                     bf.close()
  65.                     return
  66.                 }
  67.             }
  68.         }
  69.         bf.write("NO")
  70.         bf.close()
  71.  
  72.     }
  73.  
  74. }
  75.  
  76. fun main() {
  77.     val task = Task()
  78.     task.findCycle()
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement