# PBinfo #963 – Bazine – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## 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 bazine.in 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 bazine.out 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

Exemplu:
bazine.in

10 8
1 6
4 5
8 6
3 7
9 4
1 8
10 6
1 10
bazine.out

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

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
int v[105],fr[105];
int main()
{ 
	ifstream f("bazine.in");
	ofstream g("bazine.out");
	int n,i,j,a,b,p,k,m;
	f>>n>>m;
	for(i=1;i<=n;i++)
		v[i]=i;
	for(k=1;k<=m;k++)
	{
		f>>i>>j;
		if(v[i]!=v[j])
		{
			a=v[i];
			if(a<=v[j])
				b=v[j];
			else 
			{
				b=a; a=v[j];
			}
			for(p=1;p<=n;p++)
				if(v[p]==b)
					v[p]=a;
		}
	}
	k=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(v[j]==i)
			{
				k++;
				break;
			}
	g<<k<<endl;
	f.close();
	g.close();
	return 0;}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/963)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/963/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-963/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)