4204 - Este Arbore
Cerinţa[edit | edit source]
Verificați dacă un graf este arbore sau nu.
Date de intrare[edit | edit source]
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[edit | edit source]
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[edit | edit source]
- 1 ⩽ n ⩽ 100
- 1 ⩽ x, y ⩽ n
- muchiile se pot repeta
Exemplul 1[edit | edit source]
- 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[edit | edit source]
- estearborein.txt
5 1 2 2 3 3 4 4 105 5 1
- estearboreout.txt
Datele de intrare nu corespund restrictiilor impuse
Rezolvare[edit | edit source]
<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[edit | edit source]
Graful poate fi arbore.