Reconstrução da hierarquia de departamentos a partir de pares de subordinação

Python Hard dicts

Tarefa «Reconstrução da hierarquia de departamentos a partir de pares de subordinação»

São fornecidos pares de subordinação de funcionários no formato 'chefe:subordinado'. É necessário reconstruir a estrutura hierárquica completa dos departamentos. Cada funcionário pode ter vários subordinados, mas apenas um chefe (exceto o diretor raiz). Os dados de entrada podem conter ciclos ou dados incompletos — esses casos devem ser ignorados. Para cada departamento (o chefe mais alto na cadeia), imprimir a lista de todos os funcionários desse departamento em ordem alfabética, separados por espaço. Os departamentos devem ser ordenados pelo nome do chefe do departamento.

Formato de Entrada

A primeira linha contém um número inteiro N (1 ≤ N ≤ 10000) — o número de pares. Em seguida, N linhas, cada uma no formato: 'chefe:subordinado' (letras latinas, comprimento de 1 a 20 caracteres).

Formato de Saída

Para cada departamento, imprimir uma linha: 'chefe do departamento: funcionário1 funcionário2 ...' (todos os funcionários do departamento, incluindo o próprio chefe, em ordem alfabética). Os departamentos devem ser ordenados pelo nome do chefe. Se os dados forem contraditórios (ciclo, múltiplos chefes), apenas a parte não contraditória é exibida.

Exemplos

Exemplo 1

ENTRADA

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

SAÍDA

Alice: Alice Bob Charlie David Eve

Exemplo 2

ENTRADA

3
X:Y
Y:Z
Z:X

SAÍDA

Exemplo 3

ENTRADA

2
M:N
M:O

SAÍDA

M: M N O

Exemplo 4

ENTRADA

ab3c2

SAÍDA

abababcc

main.py