🔥

ABC177 D - Friendsのメモ

2023/02/25に公開

AtCoder

競プロ

tech

目についたD問題を解いてみるの回です。

考察

とりあえず人を頂点、友人関係を辺とした無向グラフで扱えそうというのはすぐわかりました。
友達の友達なども友達と扱うということなので、要するに同じ連結成分に属していれば友達といえます。

入力例1は以下のようなグラフになります。

なので1と2と5が友達で、3と4も友達ということになります。逆に同じ連結成分に属さない人は友達ではないので、たとえば1と3は友達ではなく、1と4も友達ではありません。
「同じグループの中に友達がいない」ように分けるには、同じ連結成分に属さない人同士を同じグループにします。同じ連結成分に属している人同士を同じグループには入れられないので、グループの数は最低でも連結成分に属する頂点数（の最大値）以上になります。
上記のグラフの場合、1と2と5の3人が属する連結成分があるので、最低でも3グループは必要ということになります。

とりあえず1、2、5を別のグループに分類してみます。

3と4も割り振るとするとどうなるでしょうか。たとえば3は、1と2と5の誰とも友達ではないので、どれかに適当に割り振れます。とりあえず1と同じグループにするとします。
4も同様ではありますが、3を入れたグループには入れられません。とりあえず2と同じグループに入れることにします。

このようになり、出力例1に記載の例と一致します。答えは3グループです。

こんな感じで、連結成分を横断して1人ずつグループ化することで最小のグループ数で分けられます。

となると、上で「グループの数は最低でも連結成分に属する頂点数（の最大値）以上」と書きましたが、むしろそれが答えそのものであることがわかります。
一つのグループの中の人数には特に上限がないので、連結成分がいくつ増えても一つのグループに押し込めることができるので。

一応他の例も見てみます。
入力例2は以下のようになります。

この場合は全員が友達同士なので全員バラバラにするしかなく、答えは4です。
上記の考え方でいうと、連結成分は一つだけで、連結成分の頂点数は4なのでその4がそのまま答えになります。

入力例3は以下のような感じです。

3、1、4が属する連結成分の頂点数が3なのでそれが答えです。

なお、入力されるグラフにサイクルがある可能性もありますが、サイクルがあっても特に考え方は変わりません。
（実装上は考慮が必要ですが）

実装

各連結成分の個数を数えて、その最大値を求めればいいです。いくつか解法が考えられますが、たとえばDFSで実装すると以下のような感じです。

DFSを使った実装

連結かどうかは結局辿らないとわからないので、愚直に全部辿って各頂点を連結成分ごとに分類しているのが以下です。
（実行時間がけっこうギリギリになったので良い実装ではないです…）

1から $N$ までの全ての頂点から探索を開始、訪問済でなかったらそのから辿れる全ての頂点を一つの連結成分に属するものとして分類して探索済とする、を繰り返しています。
map を使ったごちゃごちゃしている箇所はサイクルの考慮です。（もっと良い方法があるとは思います…）

@OptIn(ExperimentalStdlibApi::class)
fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    val graph = Array(n + 1) { mutableListOf<Int>() }

    repeat(m) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        graph[a].add(b)
        graph[b].add(a)
    }

    val stack = ArrayDeque<Int>()

    val seen = BooleanArray(n + 1)

    val map = mutableMapOf<Int, MutableSet<Int>>()

    val groups = mutableListOf<MutableSet<Int>>()
    for(i in 1..n) {
        if(seen[i]) {
            continue
        }

        stack.add(i)
        seen[i] = true

        val friends = mutableSetOf<Int>()
        groups.add(friends)

        while (stack.isNotEmpty()) {
            val v = stack.removeLast()

            friends.add(v)

            for(node in graph[v]) {
                if(node in map.getOrDefault(v, mutableSetOf())) {
                    continue
                }
                map.putIfAbsent(node, mutableSetOf())
                map[node]?.add(v)

                if(seen[node]) {
                    continue
                }

                seen[node] = true
                stack.add(node)

                friends.add(node)
            }
        }
    }

    println(groups.map { it.size }.max())
}

なお、探索順は関係ないのでBFSで実装しても同じだと思います。

Union-Findを使った実装

Union-Findの実装を既に持っていれば、もっと簡単に実装できます。
こちらは実行速度も速いです。

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    val uf = UnionFind(n + 1)

    repeat(m) {
        val (a, b) = readLine()!!.split(" ").map { it.toInt() }
        uf.union(a, b)
    }

    val bucket = IntArray(n + 1)
    for(i in 1..n) {
        bucket[uf.find(i)]++
    }

    println(bucket.max())
}

private class UnionFind(n: Int){
    private val roots = IntArray(n){ it }
    private val ranks = IntArray(n){ 1 }

    fun find(i: Int): Int{
        if(roots[i] != i){
            roots[i] = find(roots[i])
        }

        return roots[i]
    }

    fun isSame(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }

    fun union(x: Int, y: Int){
        val rootX = find(x)
        val rootY = find(y)

        if(rootX == rootY) {
            return
        }
        if(ranks[rootX] > ranks[rootY]){
            roots[rootY] = rootX
            ++ranks[rootX]
        }else{
            roots[rootX] = rootY
            ++ranks[rootY]
        }
    }
}

入力を全てUnion-Findに突っ込んで内部で木を生成してもらったら、あとは各頂点がどの根に属するかを全て調べます。同じ根に属していれば連結なので、結果として返ってきた根の番号がそれぞれ何件あるかカウントしてその最大値が答えになります。

（執筆時間: 57分8秒）

考察

実装

DFSを使った実装

Union-Findを使った実装

Discussion