백준 20040번 사이클 게임 Kotlin

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

문제

---

생각하기

---

• 무방향 그래프

• 유니온 파인드

동작

사이클을 찾기 위해 유니온 파인드를 활용한다.

결과

코드

---

import java.io.File
import java.util.StringTokenizer

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

// variables
private var N = 0
private var M = 0
private lateinit var parents: IntArray
private lateinit var ranks: IntArray

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

    input()

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

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

    for (i in 0 until M) {
        val st = StringTokenizer(br.readLine())
        val a = st.nextToken().toInt()
        val b = st.nextToken().toInt()

        val rootA = find(a)
        val rootB = find(b)

        if (rootA == rootB) {
            sb.append(i + 1)
            return sb.toString()
        }

        union(a, b, rootA, rootB)
    }

    sb.append(0)
    return sb.toString()
} // End of solve()

private fun union(a: Int, b: Int, rootA: Int, rootB: Int) {
    parents[a] = rootA
    parents[b] = rootB

    if (rootA == rootB) return

    // Union by Rank (랭크 기반 합치기)
    if (ranks[rootA] < ranks[rootB]) {
        parents[rootA] = rootB
    } else if (ranks[rootA] > ranks[rootB]) {
        parents[rootB] = rootA
    } else {
        // 높이가 같을 때
        parents[rootB] = rootA
        ranks[rootA]++
    }
} // End of union()

private fun find(node: Int): Int {
    // 경로 압축(Path Compression)
    if (parents[node] != node) {
        parents[node] = find(parents[node])
    }

    return parents[node]
} // End of find()

private fun input() {
    val st = StringTokenizer(br.readLine())
    N = st.nextToken().toInt()
    M = st.nextToken().toInt()

    parents = IntArray(N) { it }
    ranks = IntArray(N)
} // End of input()