Den transponierten Graphen finden
Angenommen, Sie haben einen gerichteten Graphen mit
v Knoten und e Kanten. Ihre Aufgabe besteht darin, die Transponierung dieses Graphen zu bestimmen.Die Transponierung eines gerichteten Graphen entsteht dadurch, dass man alle Kanten umkehrt. Mit anderen Worten: In der transponierten Version eines gerichteten Graphen werden sämtliche Richtungen der ursprünglichen Kanten invertiert.
Die Transponierung eines Graphen ist nützlich, um inverse Beziehungen oder umgekehrte Pfade im Graphen zu finden. Später im Kurs werden wir einige Anwendungen genauer betrachten.
Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).In den folgenden
e Zeilen stehen jeweils zwei Ganzzahlen v1, v2 (1 ≤ v1, v2 ≤ v). Dies bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist.Ausgabe
Ihr Programm soll die Adjazenzliste des Komplementgraphen ausgeben. Jede Zeile beginnt mit der ID des Knotens, gefolgt von einem Semikolon (
:) und anschließend dessen Nachbarn. Die Nachbarn in jeder Zeile sollten durch ein Leerzeichen getrennt werden. Die Reihenfolge der Knoten sowie deren Nachbarn kann beliebig sein.Beispiele
Eingabe | Ausgabe |
4 4
1 2
1 4
2 4
3 4 | 1:
2: 1
3:
4: 1 2 3 |
Constraints
Time limit: 3.5 seconds
Memory limit: 512 MB
Output limit: 1 MB