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 ⩽ n ⩽ 100
• 1 ⩽ x, y ⩽ 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

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()

Explicatie

Graful poate fi arbore.