백준 1707번 이분 그래프 Kotlin

https://www.acmicpc.net/problem/1707

문제

---

생각하기

---

• 이분 그래프 판별 문제이다.

동작

결과

코드

---

import java.io.*
import java.util.StringTokenizer

// input
private var br = System.`in`.bufferedReader()

// variables
private var V = 0
private var E = 0
private lateinit var adjList: MutableList<MutableList<Int>>

fun main() {
    val bw = System.out.bufferedWriter()

    val t = br.readLine().toInt()
    repeat(t) {
        input()

        bw.write(solve())
    }

    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val color = IntArray(V + 1) { -1 }
    var startNode = 0
    while (startNode < V) {
        if (color[startNode] == -1) {
            if (!BFS(startNode, color)) {
                sb.append("NO").append('\n')
                return sb.toString()
            }
        }

        startNode++
    }

    sb.append("YES").append('\n')
    return sb.toString()
} // End of solve()

private fun BFS(startNode: Int, color: IntArray): Boolean {
    val que = ArrayDeque<Int>()
    que.addLast(startNode)
    color[startNode] = 0

    while (que.isNotEmpty()) {
        val cur = que.removeFirst()

        for (v in adjList[cur]) {
            if (color[v] == -1) {
                color[v] = 1 - color[cur]
                que.addLast(v)
            } else if (color[v] == color[cur]) {
                return false
            }
        }
    }

    return true
} // End of BFS()

private fun input() {
    var st = StringTokenizer(br.readLine())
    V = st.nextToken().toInt()
    E = st.nextToken().toInt()

    adjList = mutableListOf()
    repeat(V + 1) {
        adjList.add(mutableListOf())
    }

    repeat(E) {
        st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()

        adjList[a].add(b)
        adjList[b].add(a)
    }
} // End of input()