Overview

The problem asks you to examine each cable in order, determine “whether keeping this cable would create a cycle,” and count the number of cables that create cycles (= the number that must necessarily be removed).
If this count is \(K\) or less, output Yes; otherwise, output No.

Analysis

To make the graph a forest (no cycles), each connected component must be a “tree.”
In other words, we need to remove the extra edges that contribute to cycles.

The key observations are as follows:

• When two vertices are already in the same connected component, adding a new edge between them always creates a cycle
• A self-loop \((a=a)\) is also an edge “connecting within the same component” at the time of addition, so it creates a cycle
• For multiple edges, after the first edge connects the vertices, any subsequent edges between them create cycles

Therefore, by processing edges one by one: - Edges that connect different components can be “kept” - Edges that connect within the same component “need to be removed”

Counting this way directly gives us the required number of removals.

A naive approach of “removing one edge and checking for cycles” repeatedly would require DFS/BFS each time, which is too slow (up to \(N=2\times10^5\)).
Instead, by using Union-Find (DSU), which can perform connectivity checks and merges efficiently, we can process each edge in nearly constant time.

Algorithm

1. Initialize a DSU with vertices \(1..N\).
2. Prepare need_remove = 0.
3. For each cable \((a,b)\):
   • Attempt unite(a,b).
   • If they are already in the same set, unite fails (returns false), meaning this edge creates a cycle.
     Increment need_remove++.
   • If they are in different sets, the merge succeeds (returns true). This edge can be kept.
4. Finally, if need_remove <= K, output Yes; otherwise, output No.

This need_remove equals “the minimum number of edges that must be removed to eliminate all cycles.”
This is because the failed edges cannot be part of any forest, while collecting only the successful edges forms a forest.

Complexity

• Time complexity: \(O(N \alpha(N))\) (\(\alpha\) is the inverse Ackermann function, which is extremely small)
• Space complexity: \(O(N)\)

Implementation Notes

• Since vertex numbering starts from \(1\), set the DSU array size to n+1.

• Using the return value of unite(a,b) directly makes the implementation concise:

  • If false, increment the removal count.

• Self-loops and multiple edges require no special handling. The DSU check naturally counts them as “edges within the same set.”

  Source Code

#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;
}

This editorial was generated by gpt-5.3-codex.