0636 – Arbore
De la Universitas MediaWiki
Cerința
Se dau cele n-1
muchii ale unui arbore cu n
noduri și un nod k
. Afișați vectorul de tați al arborelui cu rădăcina în k
.
Date de intrare
Fișierul de intrare arboreIN.txt
conține pe prima linie numerele n k
, Următoarele n-1
linii vor conține câte o pereche i j
, reprezentând muchiile arborelui.
Date de ieșire
Fișierul de ieșire arboreOUT.txt
va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în k
, separate printr-un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".
Restricții și precizări
1 ≤ n ≤ 100
1 ≤ k ≤ n
- în vectorul de tați rădăcina este marcată cu
0
Exemplul 1 :
arboreIN.txt
7 4 1 2 1 4 1 7 3 7 5 7 6 7
arboreOUT.txt
4 1 7 0 7 7 1
Exemplul 2 :
arboreIN.txt
1000 1001 1 2 1 4 1 7 3 7 5 7 6 7
arboreOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def verifica_restrictii(n, k, muchii):
if not (1 <= n <= 100) or not (1 <= k <= n) or len(muchii) != n - 1:
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
# Verifică dacă nodurile din muchii sunt în intervalul corect
for muchie in muchii:
if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
return True
def dfs(nod, parinte, graf, rezultat):
rezultat[nod] = parinte
for vecin in graf[nod]:
if vecin != parinte:
dfs(vecin, nod, graf, rezultat)
def main():
# Citirea datelor de intrare
with open("arboreIN.txt", "r") as file_in:
n, k = map(int, file_in.readline().split())
muchii = [tuple(map(int, file_in.readline().split())) for _ in range(n - 1)]
# Verificarea restricțiilor
if not verifica_restrictii(n, k, muchii):
return
# Construirea grafului
graf = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])
# Inițializarea vectorului de tați cu 0
parinti = [0] * (n + 1)
# Apelarea algoritmului DFS
dfs(k, 0, graf, parinti)
# Scrierea rezultatului în fișierul de ieșire
with open("arboreOUT.txt", "w") as file_out:
file_out.write(" ".join(map(str, parinti[1:])))
if __name__ == "__main__":
main()