|
|
| Line 1: |
Line 1: |
| == 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<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>
| |
