Simina at 12:58, 7 January 2024

2024-01-07T12:58:17Z

← Older revision		Revision as of 12:58, 7 January 2024
Line 24:		Line 24:
	= Exemplul 1 =		= Exemplul 1 =
	<code>bazineIN.txt</code>		<code>bazineIN.txt</code>
	5		10 8
	1 6		1 6
	4 5		4 5

Simina: Pagină nouă: == 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...

2023-12-13T13:06:01Z

Pagină nouă: == Enunț == La ştrandul Junior din oraşul nostru s-au construit <code>n</code> bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între <code>m</code> 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...

New page

== Enunț ==
La ştrandul Junior din oraşul nostru s-au construit <code>n</code> bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între <code>m</code> 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 <code>1</code> la <code>n</code> şi a notat în registrul lui cele <code>m</code> perechi de numere <code>(x1,y1)</code>, <code>(x2,y2)</code>,…., <code>(xm,ym)</code> 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 <code>n</code> şi <code>m</code>, şi cele <code>2*m</code> numere naturale <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>,…., <code>xm</code>, <code>ym</code>, cu semnificația din enunț, şi care să afişeze cel mai mic număr <code>k</code> 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 <code>bazineIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar pe următoarele <code>m</code> linii căte o pereche de numere <code>x y</code>.

= Date de ieșire =
Fișierul de ieșire <code>bazineOUT.txt</code> va conține pe prima linie numărul <code>k</code> determinat.

= Restricții și precizări =

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

= Exemplul 1 =
<code>bazineIN.txt</code>
5
1 6
4 5
8 6
3 7
9 4
1 8
10 6
1 10
<code>bazineOUT.txt</code>
4

= Explicație =
Apa din bazinele <code>1</code>, <code>6</code>, <code>8</code> şi <code>10</code> 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 <code>4</code>, <code>5</code> şi <code>9</code> comunică, deoarece între acestea sunt ţevi. Astfel pentru aceste bazine este necesar să se deschidă un singur robinet.

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

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

În total se deschid doar <code>4</code> robinete pentru a alimenta toate bazinele

== Exemplul 2 ==
<code>bazineIN.txt</code>
5 5
<code>bazineOUT.txt</code>
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>

0963 - Bazine - Revision history

Simina at 12:58, 7 January 2024