Advertisement
Guest User

Untitled

a guest
Feb 25th, 2020
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.09 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"+System.lineSeparator())
  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