gincana.cpp

//solucao de Davi Gabriel

#include <bits/stdc++.h>
#define MAXN 1010

using namespace std;

int mark[MAXN];                 //Declaro o que será necessário
vector < int > vizinhos[MAXN];

void DFS(int x){ //Crio a DFS

    mark[x] = 1;

    for(int i = 0; i < vizinhos[x].size(); i++){

        int f = vizinhos[x][i];

        if(mark[f] == -1){

            DFS(f);
        }
    }
}

int main() {

    int n, m, ans = 0;

    cin >> n >> m;

    memset(mark, -1, sizeof(mark)); //Inicializo como se nenhum vertice fosse visitado

    for(int i = 0; i < m; i++){

        int p, q;

        cin >> p >> q;

        vizinhos[p].push_back(q);   //Registro a aresta que liga os vértices p e q
        vizinhos[q].push_back(p);   //Ou seja, registro que são amigos
    }

    for(int i = 1; i <= n; i++){

        if(mark[i] == -1){

            DFS(i); //Se temos um vertice que ainda nao foi visitado apos a DFS do anterior entao
                   //Temos um novo grupo de amigos, inimigos dos anteriores, assim o numero de
                  //grupos aumenta em 1 unidade

            ans++; //Incremento a resposta
        }
    }

    cout << ans << "\n";

    return 0;
}