Overview

This problem asks whether we can remove at most \(K\) edges from a graph with \(N\) vertices and \(N\) edges to make it a “forest (a graph with no cycles).” It can be solved using the fundamental graph theory property relating the number of vertices, edges, and connected components.

Analysis

1. Properties of a Forest (Acyclic Graph)

In a forest with \(N\) vertices and \(C\) connected components, the number of edges \(E\) is given by the following formula: $\(E = N - C\)\( This formula is an extension of the fact that a single tree (a connected acyclic graph) has \)E = N - 1$, generalized to multiple connected components.

2. Minimum Number of Edges to Remove to Eliminate All Cycles

Let the given graph have \(N\) vertices, \(|E|\) edges, and \(C\) connected components. Consider removing some edges from this graph to make it a forest without changing the number of connected components (i.e., while maintaining the original connectivity). In this case, the maximum number of edges that can remain is \(N - C\) as described above.

Therefore, the minimum number of edges that must be removed to eliminate all cycles is: $\(\text{(original number of edges)} - \text{(maximum edges in a forest)} = |E| - (N - C)\)$

In this problem, \(|E| = N\), so: $\(N - (N - C) = C\)\( Thus, **the number of connected components \)C$ equals the minimum number of edges that must be removed.**

3. Summarizing the Condition

The problem asks “can we make it a forest by removing at most \(K\) edges?” Since we can make it a forest by removing a minimum of \(C\) edges, the condition can be simply restated as: $\(C \leq K\)$

Note: Even when self-loops or multiple edges exist, as long as the number of connected components is counted correctly, this formula correctly gives the “number of moves needed to eliminate cycles.”

Algorithm

We use Union-Find (Disjoint Set Union) to find the number of connected components \(C\).

1. Initialize a Union-Find structure with \(N\) vertices. In the initial state, each vertex is independent, so the number of connected components is \(C = N\).
2. For each edge \((A_i, B_i)\), do the following:
   • If vertices \(A_i\) and \(B_i\) do not yet belong to the same group, unite them and decrease the number of connected components \(C\) by 1.
   • If they already belong to the same group, do nothing (the number of connected components does not change).
3. If the final \(C\) is at most \(K\), output Yes; otherwise, output No.

Complexity

• Time Complexity: \(O(N \alpha(N))\)
  • We iterate over \(N\) edges and perform a Union-Find operation for each. \(\alpha\) is the inverse Ackermann function, which grows so slowly that it can be considered a constant in practice.
• Space Complexity: \(O(N)\)
  • We use \(O(N)\) memory for arrays managing parent nodes in Union-Find.

Implementation Notes

• Managing Connected Components: It is convenient to maintain a variable (num_components) within the Union-Find structure that decreases each time a successful union is performed, making it easy to retrieve the number of connected components at the end.

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in C++ it is common to speed up I/O using cin.tie(nullptr); ios::sync_with_stdio(false);.

  Source Code

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

---

This editorial was generated by gemini-3-flash-thinking.