Reference solution also fails in the edge case of n = 1, which should be [0, 0] because nothing needs to be added:

conexiDad.problem(1, 0, [])
expected:<[2, 0]> but was:<[0, 0]>

The simplest test case:

conexiDad.problem(6, 2, [4, 3, 5, 6])
expected:<[2, 3]> but was:<[1, 3]>

which can be solved by (1, 4), (2, 6), (3, 5).

Reference solution is incorrect:

conexiDad.problem(9, 4, [5, 9, 8, 6, 6, 3, 7, 3])
expected:<[2, 4]> but was:<[1, 4]>

max_extra is provably 1 by the following construction:

(1, 3)
(2, 6)
(4, 7)
(5, 8)

There are only 5 random tests. Incorrect calculation of the first return value can still pass the random tests often.

Source: OJI 2019 XI-XII, Problem 1

Thx for working on my suggestion.
After seeing your solution there is an edge case with two nodes and zero edges. I suggest to put this one in the test suite, if it is not already there.
Cheers!

Thank you for your suggestion, I changed the N to n, and regarding the use of m, I added it as an argument for an easier understanding of the problem and for the examples.

The argument m for the number of edges is almost redundant with the array that contains the edges. You could consider dropping m as an argument.
And a minor one, but in the description n and N are used for the same argument.

It looks challenging enough to give it a try!

Yes it seems I forgot to add this detail, I now stated clearly that the max_extra needs to be minimum, thank you for your input.

But there's nothing about that it has to be minizimed. The only word "minimum" is in

Add a minimum number of edges to the graph so that it becomes connected.

I did add the minimum number of edges possible. Then max_extra is 99 and the description guarantees that it's always the same (it's not the same in general, so it looks like a constraint on input), so I chose an arbitrary solution.

Yes it will, but max_extra needs to be the minimum amount of edges added to a specific node so that the graph becomes connected, so u could connect everything with 1 but it isn't a valid solution.

Keep in mind that there are MULTIPLE SOLUTIONS for how the newly added edges can be placed so the graph becomes connected, but the max_extra will always remain the same so there are no problems.

ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(2,99));
assertEquals(arr, conexiDad.problem(100,0,null));

If I connect everything with 1, max_extra will be 99, won't it?

already far better

Tho, I'd suggest that you show another situation for the second example:

1-2-3-4-5  => 3 added edges (total), and now, it's extra2 that is equal to 2.

I changed the returned type to List and it seems like I should also add some random tests, especially for ZED.CWT :)