Editing 4204 - Este Arbore

== 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.