0963 - Bazine

Enunț

La ştrandul Junior din oraşul nostru s-au construit n bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între m perechi distincte de bazine, a fost instalată câte o ţeavă prin care apa din cele două bazine din fiecare pereche să poată circula. Astfel, cele două bazine din pereche pot fi umplute prin deschiderea unui singur robinet.

Administratorul bazei a numerotat bazinele cu numerele distincte de la 1 la n şi a notat în registrul lui cele m perechi de numere (x1,y1), (x2,y2),…., (xm,ym) corespunzând perechilor de bazine între care a fost instalată câte o ţeavă. Pentru a umple toate bazinele cu apă, administratorul doreşte să deschidă un număr minim de robinete.

Cerinţă.

Scrieţi un program care să citească numerele naturale n şi m, şi cele 2*m numere naturale x1, y1, x2, y2,…., xm, ym, cu semnificația din enunț, şi care să afişeze cel mai mic număr k de robinete pe care trebuie să le deschidă administratorul astfel încât să fie umplute cu apă toate bazinele.

Date de intrare

Fișierul de intrare bazineIN.txt conține pe prima linie numerele n m, iar pe următoarele m linii căte o pereche de numere x y.

Date de ieșire

Fișierul de ieșire bazineOUT.txt va conține pe prima linie numărul k determinat.

Restricții și precizări

• 10 ≤ n ≤ 100
• 8 ≤ m ≤ 400
• nu există două perechi de numere (x,y), (x’,y’) astfel încât x=x’ şi y=y’ sau x=y’ şi y=x’ printre cele m perechi citite din fişier
• 1 ≤ xi ≤ n , 1 ≤ yi ≤ n , xi ≠ yi
• fiecare bazin poate fi cuplat la unul sau mai multe bazine prin câte o ţeavă, sau la nici un bazin

Exemplul 1

bazineIN.txt

10 8
1 6
4 5
8 6
3 7
9 4
1 8
10 6
1 10

bazineOUT.txt

4

Explicație

Apa din bazinele 1, 6, 8 şi 10 comunică doar între acestea, fiind instalate ţevi. Astfel pentru aceste patru bazine este necesar să se deschidă un singur robinet pentru umplerea lor.

Apa din bazinele 4, 5 şi 9 comunică, deoarece între acestea sunt ţevi. Astfel pentru aceste bazine este necesar să se deschidă un singur robinet.

Pentru bazinele 3 şi 7 între care există teavă, se deschide un singur robinet, cele două bazine nefiind legate prin ţevi de celelalte bazine

Bazinul 2 nu este cuplat cu niciun alt bazin, fiind necesar să se deschidă robinetul acestuia.

În total se deschid doar 4 robinete pentru a alimenta toate bazinele

Exemplul 2

bazineIN.txt

5 5

bazineOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare<syntaxhighlight lang="python3" line="1"> class Graf:

   def __init__(self, varfuri):
       self.varfuri = varfuri
       self.lista_adiacenta = {i: [] for i in range(1, varfuri + 1)}

   def adauga_muchie(self, u, v):
       self.lista_adiacenta[u].append(v)
       self.lista_adiacenta[v].append(u)

   def numar_minim_robinete(self):
       vizitate = set()
       robinete = 0

       for varf in range(1, self.varfuri + 1):
           if varf not in vizitate:
               robinete += 1
               self.dfs(varf, vizitate)

       return robinete

   def dfs(self, varf, vizitate):
       vizitate.add(varf)
       for vecin in self.lista_adiacenta[varf]:
           if vecin not in vizitate:
               self.dfs(vecin, vizitate)

def verifica_restrictii(n, m, perechi):

   if not(10 <= n <= 100) or not(8 <= m <= 400):
       return False

   for i in range(m):
       x, y = perechi[i]
       if not(1 <= x <= n) or not(1 <= y <= n) or x == y:
           return False

   for i in range(m):
       for j in range(i + 1, m):
           if set(perechi[i]) == set(perechi[j]):
               return False

   return True

if __name__ == "__main__":

   with open("bazineIN.txt", "r") as fisier_intrare:
       n, m = map(int, fisier_intrare.readline().split())
       perechi = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(m)]

       if not verifica_restrictii(n, m, perechi):
           with open("bazineOUT.txt", "w") as fisier_iesire:
               fisier_iesire.write("Datele nu corespund restrictiilor impuse")
       else:
           graf = Graf(n)

           for x, y in perechi:
               graf.adauga_muchie(x, y)

           with open("bazineOUT.txt", "w") as fisier_iesire:
               k = graf.numar_minim_robinete()
               fisier_iesire.write(str(k))

</syntaxhighlight>