概要

\(N\) 頂点 \(N\) 辺のグラフから、最大 \(K\) 本の辺を取り除いて「森（閉路を持たないグラフ）」にできるかを判定する問題です。グラフ理論の基本的な性質である「頂点数、辺の数、連結成分の数の関係」を利用して解くことができます。

考察

1. 森（閉路のないグラフ）の性質

頂点数が \(N\)、連結成分の数が \(C\) であるような森において、辺の数 \(E\) は以下の式で表されます。 $\(E = N - C\)\( この式は、1つの木（連結な閉路のないグラフ）において \)E = N - 1$ であることを、複数の連結成分に拡張したものです。

2. 閉路をなくすために取り除くべき最小の辺数

与えられたグラフの頂点数を \(N\)、辺の数を \(|E|\)、連結成分の数を \(C\) とします。 このグラフからいくつかの辺を取り除いて、連結成分の数を変えずに（＝元の連結性を維持したまま）森にすることを考えます。このとき、残せる辺の最大数は上記の通り \(N - C\) 本です。

したがって、閉路をすべて解消するために取り除く必要がある最小の辺数は、以下のようになります。 $\(\text{(元の辺の数)} - \text{(森として残せる最大辺数)} = |E| - (N - C)\)$

今回の問題では \(|E| = N\) なので、 $\(N - (N - C) = C\)\( となり、**連結成分の数 \)C$ が、取り除くべき最小の辺数**に一致します。

3. 条件の整理

問題文では「\(K\) 本以下取り除いて森にできるか」を問われています。 最小で \(C\) 本取り除けば森にできるため、条件は以下のようにシンプルに言い換えられます。 $\(C \leq K\)$

※自己ループや多重辺がある場合も、連結成分の数さえ正しく数えれば、この数式で「閉路を解消するために必要な手数」が正しく求まります。

アルゴリズム

連結成分の数 \(C\) を求めるために、Union-Find (素集合データ構造) を使用します。

1. \(N\) 頂点の Union-Find 木を初期化する。初期状態では各頂点が独立しているため、連結成分の数 \(C = N\) である。
2. 各辺 \((A_i, B_i)\) について以下を行う：
   • 頂点 \(A_i\) と \(B_i\) がまだ同じグループに属していないなら、それらを統合（unite）し、連結成分の数 \(C\) を 1 減らす。
   • 既に同じグループに属している場合は、そのまま（連結成分の数は変わらない）。
3. 最終的な \(C\) が \(K\) 以下であれば Yes、そうでなければ No を出力する。

計算量

• 時間計算量: \(O(N \alpha(N))\)
  • \(N\) 本の辺を走査し、それぞれに対して Union-Find の操作を行います。\(\alpha\) はアッカーマン関数の逆関数で、実用上は定数と見なせるほど非常に低速に増加します。
• 空間計算量: \(O(N)\)
  • Union-Find の親ノードを管理する配列などで \(O(N)\) のメモリを使用します。

実装のポイント

• 連結成分の管理: Union-Find の構造体の中で、統合が成功するたびにカウントを減らす変数（num_components）を持っておくと、最後に連結成分の数を取得しやすくなります。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、C++ の場合は cin.tie(nullptr); ios::sync_with_stdio(false); を使用して入出力を高速化するのが一般的です。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

/**
 * Union-Find (Disjoint Set Union) structure to keep track of connected components.
 * This implementation uses path compression and union-by-size for efficiency.
 */
struct DSU {
    vector<int> parent;
    vector<int> sz;
    int num_components;

    /**
     * Initialize DSU with n elements, each in its own component.
     * @param n The number of elements (computers).
     */
    DSU(int n) : num_components(n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
    }

    /**
     * Find the root representative of the set containing x.
     * Uses path compression to keep the tree flat.
     * @param x The element to find.
     * @return The root of the set containing x.
     */
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    /**
     * Unite the sets containing x and y.
     * Uses union-by-size to keep the tree depth small.
     * @param x First element.
     * @param y Second element.
     */
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (sz[rootX] < sz[rootY]) swap(rootX, rootY);
            parent[rootY] = rootX;
            sz[rootX] += sz[rootY];
            num_components--;
        }
    }
};

/**
 * The problem asks if we can remove at most K cables from a network of N nodes and N edges
 * such that the resulting graph is a forest (has no cycles).
 * 
 * A forest with N nodes and C connected components has exactly N - C edges.
 * In our graph G = (V, E), where |V| = N and |E| = N, the maximum number of edges
 * we can keep from the original set while forming a forest is N - C, where C is the
 * number of connected components in the original graph G.
 * 
 * Thus, the minimum number of edges we must remove to eliminate all cycles is:
 * Total Edges - Max Edges in a Forest = N - (N - C) = C.
 * 
 * Therefore, we can make the network a forest if and only if C <= K.
 */
int main() {
    // Faster input/output for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    // Read the number of computers N and the limit of cables to remove K
    if (!(cin >> N >> K)) return 0;

    DSU dsu(N);
    // Read the N cables and process them to find the number of connected components
    for (int i = 0; i < N; ++i) {
        int u, v;
        cin >> u >> v;
        dsu.unite(u, v);
    }

    // The condition to be able to form a forest by removing at most K cables is C <= K
    if (dsu.num_components <= K) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。