Rekonstruktion der Abteilungshierarchie aus Unterordnungsbeziehungen

Python Hard dicts

Aufgabe «Rekonstruktion der Abteilungshierarchie aus Unterordnungsbeziehungen»

Gegeben sind Paare von Unterordnungsbeziehungen der Mitarbeiter im Format 'Vorgesetzter:Untergebener'. Es ist die vollständige hierarchische Struktur der Abteilungen wiederherzustellen. Jeder Mitarbeiter kann mehrere Untergebene, aber nur einen Vorgesetzten haben (außer dem obersten Leiter). Die Eingabedaten können Zyklen oder unvollständige Daten enthalten – solche Fälle sind zu ignorieren. Für jede Abteilung (der oberste Vorgesetzte in der Kette) ist eine Liste aller Mitarbeiter dieser Abteilung in alphabetischer Reihenfolge, getrennt durch Leerzeichen, auszugeben. Die Abteilungen sind nach dem Namen des Abteilungsleiters zu sortieren.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (1 ≤ N ≤ 10000) – die Anzahl der Paare. Dann folgen N Zeilen, jede im Format: 'Vorgesetzter:Untergebener' (lateinische Buchstaben, Länge von 1 bis 20 Zeichen).

Ausgabeformat

Für jede Abteilung eine Zeile im Format ausgeben: 'Abteilungsleiter: Mitarbeiter1 Mitarbeiter2 ...' (alle Mitarbeiter der Abteilung, einschließlich des Leiters selbst, in alphabetischer Reihenfolge). Die Abteilungen sind nach dem Namen des Leiters zu sortieren. Wenn die Daten widersprüchlich sind (Zyklus, mehrere Vorgesetzte), wird nur der widerspruchsfreie Teil ausgegeben.

Beispiele

Beispiel 1

EINGABE

4
Alice:Bob
Alice:Charlie
Bob:David
Charlie:Eve

AUSGABE

Alice: Alice Bob Charlie David Eve

Beispiel 2

EINGABE

3
X:Y
Y:Z
Z:X

AUSGABE

Beispiel 3

EINGABE

2
M:N
M:O

AUSGABE

M: M N O

Beispiel 4

EINGABE

ab3c2

AUSGABE

abababcc

main.py