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

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