概要

\(N\) 頂点 \(N\) 辺の無向グラフから、\(K\) 本以下の辺を取り除いて森にできるか判定します。
重要なのは、「取り除く必要がある最小本数」はグラフの連結成分数に等しい、という点です。

考察

森とは、閉路を含まないグラフのことです。

ある連結成分について考えます。
その連結成分に含まれる頂点数を \(v\)、辺数を \(e\) とします。

連結な \(v\) 頂点の森、つまり木が持てる辺数は最大で \(v-1\) 本です。
したがって、この連結成分を閉路なしにするには、少なくとも

\(e - (v-1)\)

本の辺を取り除く必要があります。

これをすべての連結成分について足し合わせます。
連結成分数を \(C\)、グラフ全体の頂点数を \(N\)、辺数も \(N\) とすると、

\(\sum e = N\)

\(\sum v = N\)

なので、必要な削除本数の合計は

\(\sum \{ e - (v-1) \} = \sum e - \sum v + C = N - N + C = C\)

となります。

つまり、この問題では

森にするために必要な最小削除本数 = 連結成分数

です。

よって、連結成分数を \(C\) とすると、答えは

\(C \leq K\)

なら Yes、そうでなければ No です。

自己ループや多重辺があってもこの考え方は成り立ちます。

• 自己ループは単独で閉路なので、必ず削除対象になります
• 多重辺も閉路を作る場合があります
• しかし、どちらも「辺数が余分にある」として上の式に含まれます

素朴に「閉路を見つけて削除する」ことを繰り返す方法では、実装が複雑になりやすく、最悪計算量も大きくなります。
一方で、この問題では連結成分数だけ分かればよいため、Union-Find を使えば効率よく解けます。

アルゴリズム

Union-Find を使って、与えられた \(N\) 本の辺による連結成分を求めます。

1. 各頂点をそれぞれ独立した集合として初期化する
2. 各辺 \((A_i, B_i)\) について、\(A_i\) と \(B_i\) を Union する
   • すでに同じ集合に属している場合は何もしない
   • 自己ループの場合も同じ頂点なので何もしない
3. 最終的に根になっている頂点の数を数え、これを連結成分数 \(C\) とする
4. \(C \leq K\) なら Yes、そうでなければ No

例えば、連結成分数が \(3\) なら、森にするには最小で \(3\) 本の辺を削除する必要があります。
このとき \(K \geq 3\) なら可能、\(K < 3\) なら不可能です。

計算量

• 時間計算量: \(O(N \alpha(N))\)
• 空間計算量: \(O(N)\)

ここで \(\alpha(N)\) はアッカーマン関数の逆関数で、実用上はほぼ定数とみなせます。

実装のポイント

Union-Find では、以下の工夫をしています。

• find で経路圧縮を行う
• union 時にサイズの大きい集合へ小さい集合を併合する

これにより、十分高速に連結成分を管理できます。

また、入力の頂点番号は \(1\) 始まりなので、実装では \(0\) 始まりに直して扱っています。

ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())

    parent = list(range(N))
    size = [1] * N

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for _ in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ra = find(a)
        rb = find(b)
        if ra != rb:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]

    components = sum(1 for i in range(N) if find(i) == i)

    print("Yes" if components <= K else "No")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。