Brianna Waltner: Pagină nouă: == Cerinţa == Verificați dacă un graf este arbore sau nu. == Date de intrare == Fișierul de intrare '''estearborein.txt''' conține pe prima linie numărul de noduri '''n''', iar pe următoarele linii perechi de numere '''x y''', separate printr-un spațiu, cu semnificația că există muchie de la nodul '''x''' la nodul '''y'''. == Date de ieșire == Fișierul de ieșire '''estearboreout.txt''' va conține pe prima linie cuvântul '''DA''' dacă graful poate fi arbore, s...

2024-01-03T22:01:29Z

Pagină nouă: == Cerinţa == Verificați dacă un graf este arbore sau nu. == Date de intrare == Fișierul de intrare '''estearborein.txt''' conține pe prima linie numărul de noduri '''n''', iar pe următoarele linii perechi de numere '''x y''', separate printr-un spațiu, cu semnificația că există muchie de la nodul '''x''' la nodul '''y'''. == Date de ieșire == Fișierul de ieșire '''estearboreout.txt''' va conține pe prima linie cuvântul '''DA''' dacă graful poate fi arbore, s...

New page

== Cerinţa ==
Verificați dacă un graf este arbore sau nu.
== Date de intrare ==
Fișierul de intrare '''estearborein.txt''' conține pe prima linie numărul de noduri '''n''', iar pe următoarele linii perechi de numere '''x y''', separate printr-un spațiu, cu semnificația că există muchie de la nodul '''x''' la nodul '''y'''.
== Date de ieșire ==
Fișierul de ieșire '''estearboreout.txt''' va conține pe prima linie cuvântul '''DA''' dacă graful poate fi arbore, sau cuvântul '''NU''' dacă graful nu este arbore.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100'''
* '''1 &les; x, y &les; n'''
* muchiile se pot repeta
== Exemplul 1 ==
;'''estearborein.txt'''
5
1 3
2 4
3 1
3 5
4 2
4 5
;'''estearboreout.txt'''
Datele de intrare corespund restrictiilor impuse
DA
== Exemplul 1 ==
;'''estearborein.txt'''
5
1 2
2 3
3 4
4 105
5 1
;'''estearboreout.txt'''
Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
from collections import defaultdict

def este_arbore(numar_noduri, lista_muchii):
vizitat = [False] * (numar_noduri + 1)
graf = defaultdict(list)

for nod_x, nod_y in lista_muchii:
graf[nod_x].append(nod_y)
graf[nod_y].append(nod_x)

if este_ciclu(1, -1, graf, vizitat):
return False

for i in range(1, numar_noduri + 1):
if not vizitat[i]:
return False

return True

def este_ciclu(nod, parinte, graf, vizitat):
vizitat[nod] = True

for i in graf[nod]:
if not vizitat[i]:
if este_ciclu(i, nod, graf, vizitat):
return True
elif i != parinte:
return True

return False

def main():
with open('estearborein.txt', 'r') as f:
n = int(f.readline())
muchii = []
for _ in range(n):
x, y = map(int, f.readline().split())
muchii.append((x, y))

if 1 <= n <= 100 and all(1 <= x <= n and 1 <= y <= n for x, y in muchii):
print("Datele de intrare corespund restrictiilor impuse")
with open('estearboreout.txt', 'w') as f:
if este_arbore(n, muchii):
f.write("NU\n")
else:
f.write("DA\n")
else:
print("Datele de intrare nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()
</syntaxhighlight>
== Explicatie ==
Graful poate fi arbore.

4204 - Este Arbore - Revision history