概要

各ケーブルを順に見て「そのケーブルを残すと閉路ができるか」を判定し、閉路を作ってしまうケーブル本数（= 必ず取り外す必要がある本数）を数える問題です。
この本数が \(K\) 以下なら Yes、超えるなら No です。

考察

グラフを森（閉路なし）にするには、各連結成分で「木」にしなければなりません。
つまり、閉路に寄与する余分な辺を削除すればよいです。

ここで重要な観察は次の通りです：

• 2頂点がすでに同じ連結成分にあるとき、その間に新しい辺を追加すると必ず閉路ができる
• 自己ループ \((a=a)\) も、追加時点で「同じ成分内を結ぶ辺」なので閉路
• 多重辺も、1本目で連結済みになった後の2本目以降は閉路を作る辺

したがって、辺を1本ずつ処理して、 - 異なる成分同士をつなぐ辺は「残してよい」 - 同じ成分内をつなぐ辺は「削除が必要」 と数えれば、必要削除本数がそのまま求まります。

素朴に「辺を1本消して閉路判定」を繰り返すと、毎回 DFS/BFS が必要になり重すぎます（最大 \(N=2\times10^5\)）。
そこで、連結判定と併合を高速に行える Union-Find (DSU) を使うと、ほぼ定数時間で処理できます。

アルゴリズム

1. DSU を頂点 \(1..N\) で初期化する。
2. need_remove = 0 を用意する。
3. 各ケーブル \((a,b)\) について：
   • unite(a,b) を試す。
   • すでに同じ集合なら unite は失敗（false）するので、この辺は閉路を作る辺。
     need_remove++。
   • 異なる集合なら併合成功（true）。この辺は残せる。
4. 最後に need_remove <= K なら Yes、そうでなければ No を出力。

この need_remove は「閉路をなくすために最低限消す必要がある本数」に一致します。
なぜなら、失敗した辺はどれも森には入れられない一方、成功した辺だけを集めると森になるからです。

計算量

• 時間計算量: \(O(N \alpha(N))\)（\(\alpha\) はアッカーマン関数の逆関数で非常に小さい）
• 空間計算量: \(O(N)\)

実装のポイント

• 頂点番号が \(1\) 始まりなので、DSU 配列サイズを n+1 にする。

• unite(a,b) の戻り値をそのまま使うと実装が簡潔：

  • false なら削除必要本数を増やす。

• 自己ループや多重辺は特別扱い不要。DSU の判定で自然に「同一集合内の辺」として数えられます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n) : p(n + 1), sz(n + 1, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    DSU dsu(N);
    long long need_remove = 0;

    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        if (!dsu.unite(a, b)) {
            ++need_remove;
        }
    }

    cout << (need_remove <= K ? "Yes" : "No") << '\n';
    return 0;
}

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