Adjazenzliste – Graphdarstellung
Eine der gängigsten Methoden zur Darstellung von Graphen ist die Verwendung von Adjazenzlisten. Eine Adjazenzliste stellt den Graphen als Array von Listen dar. Jedes Element des Arrays repräsentiert dabei einen Knoten im Graphen, und die mit diesem Knoten verknüpfte Liste enthält die Knoten, die zu ihm benachbart sind.
Gegeben ist der gerichtete Graph im Bild. Daraus ergibt sich folgende Adjazenzliste:
g = [
[], # Knoten 0 wird übersprungen
[2, 4], # Knoten 1
[5], # Knoten 2
[2], # Knoten 3
[], # Knoten 4
[6, 8], # Knoten 5
[4, 7], # Knoten 6
[8], # Knoten 7
[5], # Knoten 8
]
Wie man sieht, ist die Darstellung des Graphen mithilfe einer Adjazenzliste deutlich kompakter als mithilfe einer Adjazenzmatrix. Das liegt daran, dass unser Graph nicht besonders viele Kanten aufweist. In manchen Fällen, wenn die Anzahl an Kanten sehr groß ist, kann es jedoch sinnvoller sein, den Graphen in einer Adjazenzmatrix zu speichern.
Herausforderung: Kanten zu Adjazenzliste
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Deine Aufgabe ist es, die zugehörige Adjazenzliste zu erstellen.Eingabe
In der ersten Zeile der Eingabe stehen zwei ganze Zahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).In den folgenden
e Zeilen stehen jeweils zwei ganze Zahlen v1, v2 (1 ≤ v1, v2 ≤ v), die bedeuten, dass der Knoten v1 mit dem Knoten v2 und umgekehrt verbunden ist.Ausgabe
Das Programm soll die Adjazenzliste des gegebenen Graphen ausgeben. Jede Zeile soll mit der Kennung eines Knotens gefolgt von einem Semikolon (
:) beginnen und danach dessen Nachbarn enthalten. Die Nachbarn in jeder Zeile sollen getrennt durch ein Leerzeichen ausgegeben werden. Die Reihenfolge sowohl der Knoten als auch der jeweiligen Nachbarn darf beliebig sein.Beispiele
Eingabe | Ausgabe |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 1: 2 4
2: 1 3 5
3: 2
4: 1 6
5: 2 6 8
6: 4 7 5
7: 8 6
8: 5 7 |
Erklärung
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB