lcb-0076

1.000

3/3 tests· algorithms

Proposed solution

I'll solve this step by step.

## Problem Understanding

1. We have an undirected graph with N vertices and M edges
2. We want to make the graph a "forest" (which means it has no cycles)
3. We need to find the minimum number of edges to delete

## Key Insights

A forest is a collection of trees (connected components without cycles). For a forest:
- If we have k connected components, and each component has n_i vertices, then the total number of edges in a forest = Σ(n_i - 1) = (total vertices) - k = N - k
- So if we start with M edges and want to end up with (N - k) edges, we need to delete M - (N - k) = M - N + k edges

But how do we find k (number of connected components)?

## Approach

1. Find the number of connected components in the graph
2. A forest with N vertices and k connected components has exactly (N - k) edges
3. So we need to delete M - (N - k) = M - N + k edges

## Key Insight

The minimum number of edges to delete = M - (N - number_of_connected_components)

This is because:
- A tree with n vertices has exactly n-1 edges
- A forest with k components and N total vertices has N-k edges
- So we need to remove M-(N-k) edges

## Implementation Plan

1. Read input
2. Use Union-Find (Disjoint Set Union) to find connected components
3. Count number of connected components
4. Calculate result = M - N + components

Let me trace through Sample 1:
- N=4, M=4
- Edges: (1,2), (1,3), (2,4), (3,4)
- Connected components: {1,2,3,4} → 1 component
- Result = 4 - 4 + 1 = 1 ✓

## Code Implementation

```python
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.size[px] < self.size[py]:
                px, py = py, px
            self.parent[py] = px
            self.size[px] += self.size[py]
            self.components -= 1

def solution():
    N, M = map(int, input().split())
    
    uf = UnionFind(N)
    
    for _ in range(M):
        u, v = map(int, input().split())
        uf.union(u-1, v-1)  # Convert to 0-indexed
    
    # Number of connected components
    components = uf.components
    
    # Minimum edges to delete = M - (N - components)
    result = M - (N - components)
    
    print(result)

solution()
```

Test output (stdout)

...                                                                      [100%]
3 passed in 0.05s

System prompt

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.