Reconstruction de la hiérarchie des départements à partir de paires de subordination

Python Hard dicts

Tâche «Reconstruction de la hiérarchie des départements à partir de paires de subordination»

Des paires de subordination d'employés sont données au format 'supérieur:subordonné'. Il faut reconstruire la structure hiérarchique complète des départements. Chaque employé peut avoir plusieurs subordonnés, mais un seul supérieur (sauf le directeur racine). Les données d'entrée peuvent contenir des cycles ou des données incomplètes — ces cas doivent être ignorés. Pour chaque département (le supérieur le plus haut dans la chaîne), afficher la liste de tous les employés de ce département dans l'ordre alphabétique, séparés par un espace. Les départements sont triés par le nom du chef de département.

Format d\ entrée

La première ligne contient un entier N (1 ≤ N ≤ 10000) — le nombre de paires. Ensuite, N lignes, chacune au format : 'supérieur:subordonné' (caractères latins, longueur de 1 à 20 caractères).

Format de sortie

Pour chaque département, afficher une ligne : 'chef du département: employé1 employé2 ...' (tous les employés du département, y compris le chef lui-même, dans l'ordre alphabétique). Les départements sont triés par le nom du chef. Si les données sont contradictoires (cycle, plusieurs supérieurs), seule la partie cohérente est affichée.

Exemples

Exemple 1

ENTRÉE

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

SORTIE

Alice: Alice Bob Charlie David Eve

Exemple 2

ENTRÉE

3
X:Y
Y:Z
Z:X

SORTIE

Exemple 3

ENTRÉE

2
M:N
M:O

SORTIE

M: M N O

Exemple 4

ENTRÉE

ab3c2

SORTIE

abababcc

main.py