Overview

Given an undirected graph with \(N\) vertices and \(N\) edges, we determine whether it is possible to remove at most \(K\) edges to make it a forest.
The key insight is that “the minimum number of edges that need to be removed” equals the number of connected components in the graph.

Analysis

A forest is a graph that contains no cycles.

Consider a particular connected component.
Let \(v\) be the number of vertices and \(e\) be the number of edges in that connected component.

A connected forest on \(v\) vertices, i.e., a tree, can have at most \(v-1\) edges.
Therefore, to make this connected component cycle-free, we need to remove at least

\(e - (v-1)\)

edges.

We sum this over all connected components.
Let \(C\) be the number of connected components, and let the total number of vertices be \(N\) and the total number of edges also be \(N\). Then:

\(\sum e = N\)

\(\sum v = N\)

So the total minimum number of deletions required is:

\(\sum \{ e - (v-1) \} = \sum e - \sum v + C = N - N + C = C\)

In other words, for this problem:

Minimum number of deletions to make a forest = Number of connected components

Therefore, if the number of connected components is \(C\), the answer is:

Yes if \(C \leq K\), and No otherwise.

This reasoning holds even with self-loops and multiple edges.

• A self-loop is a cycle by itself, so it always needs to be removed
• Multiple edges can also form cycles
• However, both cases are accounted for in the formula above as “excess edges”

A naive approach of repeatedly “finding and deleting cycles” tends to be complex to implement and can have large worst-case complexity.
On the other hand, since this problem only requires knowing the number of connected components, it can be solved efficiently using Union-Find.

Algorithm

Use Union-Find to determine the connected components formed by the given \(N\) edges.

1. Initialize each vertex as an independent set
2. For each edge \((A_i, B_i)\), perform Union on \(A_i\) and \(B_i\)
   • If they already belong to the same set, do nothing
   • For self-loops, since it’s the same vertex, do nothing
3. Count the number of vertices that are roots, and let this be the number of connected components \(C\)
4. If \(C \leq K\), output Yes; otherwise, output No

For example, if the number of connected components is \(3\), then at minimum \(3\) edges must be removed to make a forest.
In this case, it is possible if \(K \geq 3\), and impossible if \(K < 3\).

Complexity

• Time complexity: \(O(N \alpha(N))\)
• Space complexity: \(O(N)\)

Here, \(\alpha(N)\) is the inverse Ackermann function, which can be considered virtually constant in practice.

Implementation Notes

The Union-Find implementation uses the following optimizations:

• Path compression in find
• Union by size, merging the smaller set into the larger set

This allows managing connected components sufficiently fast.

Also, since the vertex numbers in the input are 1-indexed, the implementation converts them to 0-indexed.

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())

    parent = list(range(N))
    size = [1] * N

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for _ in range(N):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ra = find(a)
        rb = find(b)
        if ra != rb:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]

    components = sum(1 for i in range(N) if find(i) == i)

    print("Yes" if components <= K else "No")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.