Reconstrucción de la jerarquía de departamentos por pares de subordinación

Python Hard dicts

Tarea «Reconstrucción de la jerarquía de departamentos por pares de subordinación»

Se dan pares de subordinación de empleados en el formato 'jefe:subordinado'. Es necesario reconstruir la estructura jerárquica completa de los departamentos. Cada empleado puede tener varios subordinados, pero solo un jefe (excepto el director raíz). Los datos de entrada pueden contener ciclos o datos incompletos; dichos casos deben ignorarse. Para cada departamento (el jefe más alto en la cadena), mostrar la lista de todos los empleados de ese departamento en orden alfabético, separados por un espacio. Los departamentos se ordenan por el nombre del jefe del departamento.

Formato de entrada

La primera línea contiene un número entero N (1 ≤ N ≤ 10000) — la cantidad de pares. Luego N líneas, cada una en el formato: 'jefe:subordinado' (letras latinas, longitud de 1 a 20 caracteres).

Formato de salida

Para cada departamento, mostrar una línea: 'jefe del departamento: empleado1 empleado2 ...' (todos los empleados del departamento, incluido el propio jefe, en orden alfabético). Los departamentos se ordenan por el nombre del jefe. Si los datos son contradictorios (ciclo, varios jefes), solo se muestra la parte no contradictoria.

Ejemplos

Ejemplo 1

ENTRADA

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

SALIDA

Alice: Alice Bob Charlie David Eve

Ejemplo 2

ENTRADA

3
X:Y
Y:Z
Z:X

SALIDA

Ejemplo 3

ENTRADA

2
M:N
M:O

SALIDA

M: M N O

Ejemplo 4

ENTRADA

ab3c2

SALIDA

abababcc

main.py