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

#include <bits/stdc++.h>

using namespace std;

ifstream cin("bazine.in");
ofstream cout("bazine.out");

int n , m , x , y , v[101];

vector<int> G[101];
vector<vector <int> > CC;

void dfs(int nod, vector<int> &C)
{
    v[nod] = 1;
    C.push_back(nod);
    for(auto y : G[nod])
        if(v[y] == 0) dfs(y,C);
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i = 1; i <= n ; i++)
        if(!v[i])
        {
            CC.push_back(vector<int>());
            dfs(i,*(CC.end()-1));
        }

    cout << CC.size();
    return 0;

}