概要

\(N\) 台のコンピュータと \(N\) 本のケーブルからなるネットワークから、\(K\) 本以下のケーブルを取り外して森（閉路のないグラフ）にできるかを判定する問題です。

考察

森の性質

森（閉路を含まないグラフ）には重要な性質があります。\(N\) 頂点で連結成分が \(C\) 個の森は、ちょうど \(N - C\) 本の辺を持ちます。つまり、辺が多すぎると必ず閉路ができるということです。

最小除去本数の特定

問題は「閉路をすべて消すために最低何本のケーブルを除去する必要があるか」に帰着されます。

辺を1本ずつ見ていったとき、以下の辺は閉路を作ります： 1. 自己ループ（\(A_i = B_i\)）：1本で閉路をなす 2. 既に連結な2頂点を結ぶ辺：その2頂点間に既にパスがあるので、辺を追加すると閉路ができる

逆に、まだ連結でない2頂点を結ぶ辺は「木の辺」として安全に残せます。これらの木の辺を集めたものが全域森（spanning forest）となり、閉路を含みません。

結論

閉路を作る辺の本数を need_remove とすると、need_remove ≤ K なら Yes、そうでなければ No です。

アルゴリズム

Union-Find（素集合データ構造） を使って、各辺が閉路を作るかどうかを効率的に判定します。

1. \(N\) 頂点の Union-Find を初期化する（各頂点が独立な成分）
2. 各ケーブル \((A_i, B_i)\) について：
   • \(A_i = B_i\)（自己ループ）の場合 → 閉路を作るので need_remove++
   • \(A_i\) と \(B_i\) が既に同じ連結成分にある場合（unite が失敗）→ 閉路を作るので need_remove++
   • それ以外 → 2つの成分を統合（木の辺として採用）
3. need_remove ≤ K なら Yes、そうでなければ No

具体例

\(N = 4, K = 1\) で辺が \((1,2), (2,3), (3,1), (3,4)\) の場合： - \((1,2)\)：1と2を統合 → 木の辺 ✓ - \((2,3)\)：2と3を統合 → 木の辺 ✓ - \((3,1)\)：1と3は既に同じ成分 → 除去必要（need_remove = 1） - \((3,4)\)：3と4を統合 → 木の辺 ✓

need_remove = 1 ≤ K = 1 なので Yes。

計算量

• 時間計算量: \(O(N \cdot \alpha(N))\)（\(\alpha\) はアッカーマン関数の逆関数で、実質 \(O(N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• 自己ループ（\(A_i = B_i\)）は unite を呼ぶ前に個別にチェックする。unite は同じ頂点に対して find を2回呼んで同じ根を返すので失敗扱いになるが、明示的にチェックするとコードの意図が明確になる。

• Union-Find には経路圧縮とランクによる統合を実装し、高速化する。

• 入力の頂点番号は 1-indexed なので、0-indexed に変換して処理する。

  ソースコード

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

struct UnionFind {
    vector<int> parent, rank_;
    UnionFind(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;
    
    UnionFind uf(N);
    int need_remove = 0;
    
    for(int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(a == b || !uf.unite(a, b)){
            need_remove++;
        }
    }
    
    cout << (need_remove <= K ? "Yes" : "No") << endl;
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。