You are given a simple undirected graph. Determine the maximum number of edges you can remove so that the number of connected components stays exactly the same as it is now. Equivalently, this is the number of edges that lie on cycles: m - (n - c) where c is the current number of connected components.
Line 1: two integers n and m (nodes and edges). Nodes are numbered 1..n.
Next m lines: two integers u v describing an undirected edge (no self-loops, no repeated edges).
One line: the maximum number of removable edges.
Example 1
Input
4 4 1 2 2 3 3 1 3 4
Expected
1
Explanation
Nodes 1-2-3 form a triangle (one extra edge beyond a tree) and 4 hangs off 3. The graph is connected (c=1), so removable = 4 - (4 - 1) = 1.
Example 2
Input
4 2 1 2 3 4
Expected
0
Explanation
Two separate edges give c=2 components with no cycles, so removable = 2 - (4 - 2) = 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →