3713 – Company Tree

Cerința

Într-o companie, angajații sunt organizați într-un arbore ierarhic, unde fiecare angajat are un manager direct, cu excepția directorului general (CEO) care nu are niciun manager. Fiecare angajat poate avea mai mulți subordonați. Sarcina ta este să implementezi un program care să determine adâncimea fiecărui angajat în arborele companiei, unde adâncimea unui angajat este numărul de niveluri de management deasupra lui (adâncimea CEO-ului este 0).

Date de intrare

Programul citește de la tastatură:

Un număr întreg n reprezentând numărul de angajați (noduri). O listă de n-1 perechi de numere întregi, fiecare pereche a b indicând că angajatul b este managerul direct al angajatului a.

Date de ieșire

Pe ecran se va afișa adâncimea fiecărui angajat, începând de la angajatul 1 până la angajatul n.

Restricții și precizări

1 ⩽ n ⩽ 100
Angajatii sunt numerotati de la 1 la 'n'.

Exemplu 1

Intrare

5
2 1
3 1
4 2
5 3

Iesire

1: 0
2: 1
3: 1
4: 2
5: 2

Rezolvare

<syntaxhighlight lang="python" line> from collections import defaultdict, deque

def citeste_date():

   try:
       n = int(input("Introduceți numărul de angajați (n): "))
       relatii = []
       for _ in range(n - 1):
           a, b = map(int, input().strip().split())
           relatii.append((a, b))
       return n, relatii
   except ValueError:
       return None, None

def construieste_arbore(n, relatii):

   arbore = defaultdict(list)
   for a, b in relatii:
       arbore[b].append(a)
   return arbore

def determina_adancimi(n, arbore, radacina):

   adancimi = [-1] * (n + 1)
   adancimi[radacina] = 0
   coada = deque([radacina])
   
   while coada:
       nod = coada.popleft()
       for vecin in arbore[nod]:
           if adancimi[vecin] == -1:
               adancimi[vecin] = adancimi[nod] + 1
               coada.append(vecin)
   
   return adancimi

def main():

   n, relatii = citeste_date()
   
   if n is None or relatii is None:
       print("Datele de intrare nu corespund restricțiilor impuse.")
       return
   
   arbore = construieste_arbore(n, relatii)
   
   # Găsiți rădăcina (CEO-ul) ca fiind nodul care nu este niciodată în poziția "a" în relațiile "a b".
   potential_radacini = set(range(1, n + 1))
   for a, b in relatii:
       if a in potential_radacini:
           potential_radacini.remove(a)
   
   radacina = potential_radacini.pop()  # CEO-ul este unicul element rămas în set
   
   adancimi = determina_adancimi(n, arbore, radacina)
   
   for i in range(1, n + 1):
       print(f"{i}: {adancimi[i]}")

if __name__ == "__main__":

   main()

</syntaxhighlight>