Overview

This problem asks whether it is possible to remove at most \(K\) cables from a network consisting of \(N\) computers and \(N\) cables to make it a forest (a graph with no cycles).

Analysis

Properties of a Forest

Forests (graphs containing no cycles) have an important property. A forest with \(N\) vertices and \(C\) connected components has exactly \(N - C\) edges. In other words, if there are too many edges, cycles will inevitably form.

Determining the Minimum Number of Removals

The problem reduces to “what is the minimum number of cables that need to be removed to eliminate all cycles?”

When examining edges one by one, the following edges create cycles: 1. Self-loops (\(A_i = B_i\)): A single edge forms a cycle by itself 2. Edges connecting two vertices that are already connected: Since a path already exists between the two vertices, adding an edge creates a cycle

Conversely, edges connecting two vertices that are not yet connected can be safely kept as “tree edges.” The collection of these tree edges forms a spanning forest, which contains no cycles.

Conclusion

If we let need_remove be the number of edges that create cycles, then the answer is Yes if need_remove ≤ K, and No otherwise.

Algorithm

We use Union-Find (Disjoint Set Union) to efficiently determine whether each edge creates a cycle.

1. Initialize a Union-Find with \(N\) vertices (each vertex is an independent component)
2. For each cable \((A_i, B_i)\):
   • If \(A_i = B_i\) (self-loop) → it creates a cycle, so need_remove++
   • If \(A_i\) and \(B_i\) are already in the same connected component (unite fails) → it creates a cycle, so need_remove++
   • Otherwise → merge the two components (adopt as a tree edge)
3. If need_remove ≤ K, output Yes; otherwise output No

Concrete Example

For \(N = 4, K = 1\) with edges \((1,2), (2,3), (3,1), (3,4)\): - \((1,2)\): Merge 1 and 2 → tree edge ✓ - \((2,3)\): Merge 2 and 3 → tree edge ✓ - \((3,1)\): 1 and 3 are already in the same component → removal needed (need_remove = 1) - \((3,4)\): Merge 3 and 4 → tree edge ✓

Since need_remove = 1 ≤ K = 1, the answer is Yes.

Complexity

• Time complexity: \(O(N \cdot \alpha(N))\) (\(\alpha\) is the inverse Ackermann function, effectively \(O(N)\))
• Space complexity: \(O(N)\)

Implementation Notes

• Self-loops (\(A_i = B_i\)) should be checked individually before calling unite. While unite would call find twice on the same vertex and return the same root (thus being treated as a failure), checking explicitly makes the code’s intent clearer.

• Implement path compression and union by rank in the Union-Find for optimization.

• Since input vertex numbers are 1-indexed, convert them to 0-indexed for processing.

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.