Das Komplement eines Graphen ermitteln
Sie haben einen ungerichteten Graphen mit
v Knoten und e Kanten gegeben. Ihre Aufgabe ist es, dessen Komplement zu bestimmen.Als Komplement eines Graphen bezeichnet man einen Graphen, in dem zwischen allen Knoten eine Kante existiert, wenn es im ursprünglichen Graphen keine Kante zwischen diesen gab. Gleichzeitig enthält das Komplement keine Kante zwischen Knoten, die im Ausgangsgraphen miteinander verbunden sind.
.png?table=block&id=18b2c681-664d-8152-8a28-eb503b8efc2f&cache=v2)
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 500) und e (1 ≤ e ≤ 100 000).Die darauffolgenden
e Zeilen enthalten Zahlenpaare v1, v2 (1 ≤ v1, v2 ≤ v). Das bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll die Adjazenzliste des Komplement-Graphen ausgeben. Jede Zeile beginnt dabei mit der ID eines Knotens, gefolgt von einem Semikolon (
:) und seiner Liste von verbundenen Knoten. Die einzelnen Verbindungen werden durch ein Leerzeichen getrennt. Sowohl die Reihenfolge der Knoten als auch die Reihenfolge ihrer Verbindungen kann beliebig sein.Beispiele
Eingabe | Ausgabe |
4 4
1 2
4 2
4 1
3 4 | 1: 3
2: 3
3: 1 2
4: |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB