Editing 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 &les; '''n''' &les; 100
* Angajatii sunt numerotati de la 1 la 'n'.
== Exemplu 1 ==
;Intrare
5<br>
2 1<br>
3 1<br>
4 2<br>
5 3

;Iesire
1: 0<br>
2: 1<br>
3: 1<br>
4: 2<br>
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>