概要

\(N\) 台のコンピュータと \(N\) 本のケーブルからなる無向グラフから、\(K\) 本以下のケーブルを取り除いて閉路のないグラフ、つまり森にできるかを判定します。

閉路をなくすために最低限取り除く必要があるケーブルの本数を求め、それが \(K\) 以下かどうかを調べます。

考察

閉路を含まない無向グラフ、つまり森では、各連結成分について「頂点数 \(v\) に対して辺数は高々 \(v-1\) 本」です。

したがって、閉路をなくすには「余分な辺」を取り除く必要があります。

例えば、次のような辺を順番に見ていくことを考えます。

• まだつながっていない 2 頂点を結ぶ辺
  → その辺を追加しても閉路はできません。
• すでに同じ連結成分に属している 2 頂点を結ぶ辺
  → その辺を追加すると閉路ができます。

後者のような辺は、森にするためには必ずどこかで取り除く必要がある「余分な辺」です。

例えば、

1 - 2
2 - 3
1 - 3

という 3 本の辺があるとき、最初の 2 本で \(1,2,3\) はすでにつながっています。
そこに \(1-3\) の辺を追加すると閉路ができるため、この辺は余分です。

また、自己ループや多重辺も同様に扱えます。

• 自己ループは、同じ頂点同士を結ぶので即座に閉路になります。
• 多重辺は、1 本目で 2 頂点がつながり、2 本目以降は閉路を作ります。

素朴に「どのケーブルを取り除くか」を全探索すると、最大で \(2^N\) 通りあり、\(N \leq 2 \times 10^5\) では到底間に合いません。

そこで、Union-Find（DSU）を使って、各辺が閉路を作るかどうかを高速に判定します。

アルゴリズム

Union-Find を用いて、辺を 1 本ずつ見ていきます。

1. 最初は、各頂点はそれぞれ別の連結成分に属しているとします。
2. 各ケーブル \((A_i, B_i)\) について、次を行います。
   • \(A_i\) と \(B_i\) がまだ別の連結成分なら、それらを結合します。
   • すでに同じ連結成分なら、このケーブルを追加すると閉路ができるので、余分なケーブルとして数えます。
3. 余分なケーブルの本数を redundant とします。
4. redundant <= K なら Yes、そうでなければ No を出力します。

Union-Find で「結合できた辺」は森を構成する辺として残せます。
一方、「結合できなかった辺」は閉路を作る辺なので、取り除く候補になります。

最終的に、結合できた辺だけを残せば閉路のない森になります。
したがって、取り除く必要がある最小本数は redundant 本です。

計算量

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

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

実装のポイント

Union-Find の unite(a, b) が成功したかどうかを返すようにしておくと実装が簡潔です。

if (!dsu.unite(A, B)) redundant++;

このように書くことで、

• 自己ループの場合
• すでに同じ連結成分にある頂点同士を結ぶ場合
• 多重辺の 2 本目以降の場合

をすべてまとめて「余分な辺」として数えられます。

ソースコード

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

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n + 1), sz(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[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);
        parent[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);
    int redundant = 0;

    for (int i = 0; i < N; i++) {
        int A, B;
        cin >> A >> B;
        if (!dsu.unite(A, B)) redundant++;
    }

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

---

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