Advertisement
vkazar

Untitled

Dec 4th, 2023 (edited)
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Kotlin 1.81 KB | None | 0 0
  1. package sprint6.fin.B
  2.  
  3. import java.io.BufferedReader
  4. import java.io.InputStreamReader
  5. import java.util.*
  6.  
  7. fun main() {
  8.     val buffer = BufferedReader(InputStreamReader(System.`in`))
  9.     val cityCount = buffer.readLine().toInt()
  10.     val graph = buildMap<Int, Visited> {
  11.         (1..cityCount).forEach { put(it, Visited(Color.WHITE, mutableSetOf())) }
  12.         repeat(cityCount - 1) {
  13.             val cityId = it + 1
  14.             buffer.readLine().forEachIndexed { index, way ->
  15.                 val toCity = index + cityId + 1
  16.                 when (way) {
  17.                     'R' -> this[cityId]!!.edges.add(toCity)
  18.                     'B' -> this[toCity]!!.edges.add(cityId)
  19.                 }
  20.             }
  21.         }
  22.     }
  23.  
  24.     for (next in graph.entries) {
  25.         if (next.value.color != Color.WHITE) continue
  26.  
  27.         val stack = Stack<Int>()
  28.         stack.add(next.key)
  29.  
  30.         while (!stack.empty()) {
  31.             val cur = stack.pop()
  32.             val curVisited = graph[cur]!!
  33.             if (curVisited.color == Color.WHITE) {
  34.                 curVisited.color = Color.GREY
  35.                 stack.push(cur)
  36.                 curVisited.edges.forEach {
  37.                     val color = graph[it]!!.color
  38.                     if (color == Color.WHITE)
  39.                         stack.push(it)
  40.                     if (color == Color.GREY) {
  41.                         println("NO")
  42.                         return
  43.                     }
  44.                 }
  45.             } else if (curVisited.color == Color.GREY) {
  46.                 curVisited.color = Color.BLACK
  47.             }
  48.         }
  49.     }
  50.     if (graph[cityCount]!!.color == Color.BLACK)
  51.         println("YES")
  52.     else println("NO")
  53. }
  54.  
  55. data class Visited(var color: Color, val edges: MutableSet<Int>)
  56.  
  57. enum class Color {
  58.     WHITE,
  59.     GREY,
  60.     BLACK
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement