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 (x₁,y₁), (x₂,y₂),…., (x_m,y_m) 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 x₁, y₁, x₂, y₂,…., x_m, y_m, 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 ≤ x_i ≤ n , 1 ≤ y_i ≤ n , x_i ≠ y_i
fiecare bazin poate fi cuplat la unul sau mai multe bazine prin câte o ţeavă, sau la nici un bazin

Exemplu

bazine.in

bazine.out

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Bazine:

#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;}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #963 Bazine

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #963 Bazine de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #963 Bazine