Es gibt N = 10 Knoten, nummeriert 0..9

Frage 1

Wie viele Region werden nach den M = 5 folgenden ungerichteten Verbingungen p-q gebildet?

p-q
3-4
4-9
8-0
2-3
5-6

Es sind 5 verschiedene Verbindungen, mit jeder Verbindung verschwindet eine Region.
Es bleiben am Schluss also 5 (10-5) Regionen.

Frage 2

Wie gross muss M mindestens sein, um N Knoten in einer einzigen Region einzubinden?
Begründen Sie Ihre Aussage.

M muss mindestens N - 1 sein.
Bei jeder neuen Verbindung verschwindet eine Region, weshalb M + 1 = N (unter idealen Bedingungen).

Frage 3

Es sei N = 100'000.
Erstellen Sie ein Java Programm, welches Verbindungspaare p-q zufällig generiert, und rechnen Sie experimentell, wie viele Paare generiert werden müssen, um alle N Knoten in einer einzigen Region einbinden zu können (unnötige Verbindungen werden nicht berücksichtigt)?

Meine Lösung scheint etwas zu viel Unnötiges zu tun, weshalb bei der Ausführung mit N = 100'000 der Fehler "java.lang.OutOfMemoryError" auftritt...

Mangels Zeit und Gesundheit habe ich die Nachforschung abgebrochen.

Frage 4

Wieviel Zeit in Sekunden braucht Ihre Java Lösung zur Frage 3?
Vergleichen Sie die Performance mit der Quickunion-Weighted Java.

Ohne funktionierende Lösung für 3 wenig sinnvoll.