Maximise number of edges to cut in connected graph

Question

This question is very similar to Leetcode's Critical Connections in a Network. Given an undirected graph, we want to find all bridges. An edge in an undirected connected graph is a bridge iff removing it disconnects the graph.

Variant

Instead of finding all bridges, I want to maximise the number of edges to remove so that the graph remains connected.

Example 1

Input: n = 5, edges = [[1, 2], [1, 3], [3, 4], [1, 4], [4, 5]]

Output: 1

Firstly, I can remove [3,4], [1,3], or [1,4]. Next, after removing either of the 3 edges, the remaining edges are all bridges. Hence, the maximum number of edges to remove so that the graph remains connected is 1.

Example 2

Input: n = 6, edges = [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [4, 6], [5, 6]]

Output: 2

Answer 1

Well this is easy, if we have E edges and N nodes in a connected graph we can remove E-N+1 edges so that graph remains connected.

How to do this?:

Just do DFS/BFS to find any spanning tree of the graph, since spanning tree is connected we can just remove all other edges.