提出 #64783417

---

ソースコード 拡げる

@OptIn(ExperimentalStdlibApi::class)
fun main() {
    val n = Sc.int()
    val m = Sc.int()

    val graph = List(n) { mutableListOf<Int>() }
    repeat(m) {
        val u = Sc.int() - 1
        val v = Sc.int() - 1
        graph[u].add(v)
        graph[v].add(u)
    }

    // 1, 2, ..., k が接続する全ての辺からなる UF
    val allUf = UnionFind(n)
    // 1, 2, ..., k 内の辺からなる UF
    val minUf = UnionFind(n)

    val ans = (0..<n).map { k ->
        for (v in graph[k]) {
            allUf.merge(k, v)
            if (v < k) minUf.merge(k, v)
        }

        if (minUf.size(0) != k + 1) {
            -1
        } else {
            allUf.size(0) - k - 1
        }
    }

    println(ans.joinToString("\n"))
}

// ==================== Libraries ====================
object Sc {
    private val buffer: ArrayDeque<String> = ArrayDeque()

    fun string(): String {
        while (buffer.isEmpty()) buffer.addAll(readln().split(" "))
        return buffer.removeFirst()
    }

    fun int(): Int = string().toInt()

    fun long(): Long = string().toLong()
}

class UnionFind(
    private val _size: Int,
) {
    /**
     * 非負 -> 親の要素
     * 負 -> その要素が代表元である集合のサイズ (符号反転)
     */
    private val parentOrSizes = IntArray(_size) { -1 }

    /** v が属する集合の代表元を返す */
    fun leader(v: Int): Int =
        if (parentOrSizes[v] < 0) {
            v
        } else {
            parentOrSizes[v] = leader(parentOrSizes[v])
            parentOrSizes[v]
        }

    /** u が属する集合と v が属する集合を合併し、新たな集合の代表元を返す */
    fun merge(
        u: Int,
        v: Int,
    ): Int {
        var u = leader(u)
        var v = leader(v)

        if (u != v) {
            if (-parentOrSizes[u] < -parentOrSizes[v]) u = v.also { v = u } // swap
            parentOrSizes[u] += parentOrSizes[v]
            parentOrSizes[v] = u
        }
        return u
    }

    /** u と v が同じ集合に属するかを返す */
    fun same(
        u: Int,
        v: Int,
    ): Boolean = leader(u) == leader(v)

    /** v が属する集合の大きさを返す */
    fun size(v: Int): Int = -parentOrSizes[leader(v)]

    /** 各集合を返す */
    @OptIn(ExperimentalStdlibApi::class)
    fun groups(): List<List<Int>> {
        val groups = List(_size) { mutableListOf<Int>() }
        for (v in 0..<_size) groups[leader(v)].add(v)
        return groups.mapNotNull { group -> if (group.isEmpty()) null else group.toList() }
    }
}

提出情報

コンパイルエラー

Main.kt:73:13: warning: name shadowed: u
        var u = leader(u)
            ^
Main.kt:74:13: warning: name shadowed: v
        var v = leader(v)
            ^

ジャッジ結果